blob: 8b2dadb119d80330cd7c2fe978468852f2249f81 [file] [log] [blame]
Ian Rogers776ac1f2012-04-13 23:36:36 -07001/*
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
Brian Carlstromfc0e3212013-07-17 14:40:12 -070017#ifndef ART_RUNTIME_VERIFIER_REGISTER_LINE_H_
18#define ART_RUNTIME_VERIFIER_REGISTER_LINE_H_
Ian Rogers776ac1f2012-04-13 23:36:36 -070019
Ian Rogers776ac1f2012-04-13 23:36:36 -070020#include <vector>
21
22#include "dex_instruction.h"
23#include "reg_type.h"
24#include "safe_map.h"
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080025#include "UniquePtr.h"
Ian Rogers776ac1f2012-04-13 23:36:36 -070026
27namespace art {
28namespace verifier {
29
30class MethodVerifier;
31
32/*
33 * Register type categories, for type checking.
34 *
35 * The spec says category 1 includes boolean, byte, char, short, int, float, reference, and
36 * returnAddress. Category 2 includes long and double.
37 *
38 * We treat object references separately, so we have "category1nr". We don't support jsr/ret, so
39 * there is no "returnAddress" type.
40 */
41enum TypeCategory {
42 kTypeCategoryUnknown = 0,
43 kTypeCategory1nr = 1, // boolean, byte, char, short, int, float
44 kTypeCategory2 = 2, // long, double
45 kTypeCategoryRef = 3, // object reference
46};
47
48// During verification, we associate one of these with every "interesting" instruction. We track
49// the status of all registers, and (if the method has any monitor-enter instructions) maintain a
50// stack of entered monitors (identified by code unit offset).
Ian Rogers776ac1f2012-04-13 23:36:36 -070051class RegisterLine {
52 public:
Ian Rogersd0fbd852013-09-24 18:17:04 -070053 static RegisterLine* Create(size_t num_regs, MethodVerifier* verifier) {
54 uint8_t* memory = new uint8_t[sizeof(RegisterLine) + (num_regs * sizeof(uint16_t))];
55 RegisterLine* rl = new (memory) RegisterLine(num_regs, verifier);
56 return rl;
Ian Rogers776ac1f2012-04-13 23:36:36 -070057 }
58
59 // Implement category-1 "move" instructions. Copy a 32-bit value from "vsrc" to "vdst".
Ian Rogers00f7d0e2012-07-19 15:28:27 -070060 void CopyRegister1(uint32_t vdst, uint32_t vsrc, TypeCategory cat)
Ian Rogersb726dcb2012-09-05 08:57:23 -070061 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -070062
63 // Implement category-2 "move" instructions. Copy a 64-bit value from "vsrc" to "vdst". This
64 // copies both halves of the register.
Ian Rogers00f7d0e2012-07-19 15:28:27 -070065 void CopyRegister2(uint32_t vdst, uint32_t vsrc)
Ian Rogersb726dcb2012-09-05 08:57:23 -070066 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -070067
68 // Implement "move-result". Copy the category-1 value from the result register to another
69 // register, and reset the result register.
Ian Rogers00f7d0e2012-07-19 15:28:27 -070070 void CopyResultRegister1(uint32_t vdst, bool is_reference)
Ian Rogersb726dcb2012-09-05 08:57:23 -070071 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -070072
73 // Implement "move-result-wide". Copy the category-2 value from the result register to another
74 // register, and reset the result register.
Ian Rogers00f7d0e2012-07-19 15:28:27 -070075 void CopyResultRegister2(uint32_t vdst)
Ian Rogersb726dcb2012-09-05 08:57:23 -070076 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -070077
78 // Set the invisible result register to unknown
Sameer Abu Asal51a5fb72013-02-19 14:25:01 -080079 void SetResultTypeToUnknown() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -070080
81 // Set the type of register N, verifying that the register is valid. If "newType" is the "Lo"
82 // part of a 64-bit value, register N+1 will be set to "newType+1".
83 // The register index was validated during the static pass, so we don't need to check it here.
Ian Rogers00f7d0e2012-07-19 15:28:27 -070084 bool SetRegisterType(uint32_t vdst, const RegType& new_type)
Ian Rogersb726dcb2012-09-05 08:57:23 -070085 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -070086
Ian Rogers2bcb4a42012-11-08 10:39:18 -080087 bool SetRegisterTypeWide(uint32_t vdst, const RegType& new_type1, const RegType& new_type2)
88 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
89
Ian Rogers776ac1f2012-04-13 23:36:36 -070090 /* Set the type of the "result" register. */
Ian Rogers00f7d0e2012-07-19 15:28:27 -070091 void SetResultRegisterType(const RegType& new_type)
Ian Rogersb726dcb2012-09-05 08:57:23 -070092 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -070093
Ian Rogers2bcb4a42012-11-08 10:39:18 -080094 void SetResultRegisterTypeWide(const RegType& new_type1, const RegType& new_type2)
95 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
96
Ian Rogers776ac1f2012-04-13 23:36:36 -070097 // Get the type of register vsrc.
98 const RegType& GetRegisterType(uint32_t vsrc) const;
99
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700100 bool VerifyRegisterType(uint32_t vsrc, const RegType& check_type)
Ian Rogersb726dcb2012-09-05 08:57:23 -0700101 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700102
Ian Rogers2bcb4a42012-11-08 10:39:18 -0800103 bool VerifyRegisterTypeWide(uint32_t vsrc, const RegType& check_type1, const RegType& check_type2)
104 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
105
Ian Rogers776ac1f2012-04-13 23:36:36 -0700106 void CopyFromLine(const RegisterLine* src) {
107 DCHECK_EQ(num_regs_, src->num_regs_);
Ian Rogersd0fbd852013-09-24 18:17:04 -0700108 memcpy(&line_, &src->line_, num_regs_ * sizeof(uint16_t));
Ian Rogers776ac1f2012-04-13 23:36:36 -0700109 monitors_ = src->monitors_;
110 reg_to_lock_depths_ = src->reg_to_lock_depths_;
111 }
112
Ian Rogersb726dcb2012-09-05 08:57:23 -0700113 std::string Dump() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700114
115 void FillWithGarbage() {
Ian Rogersd0fbd852013-09-24 18:17:04 -0700116 memset(&line_, 0xf1, num_regs_ * sizeof(uint16_t));
Ian Rogers776ac1f2012-04-13 23:36:36 -0700117 while (!monitors_.empty()) {
118 monitors_.pop_back();
119 }
120 reg_to_lock_depths_.clear();
121 }
122
123 /*
124 * We're creating a new instance of class C at address A. Any registers holding instances
125 * previously created at address A must be initialized by now. If not, we mark them as "conflict"
126 * to prevent them from being used (otherwise, MarkRefsAsInitialized would mark the old ones and
127 * the new ones at the same time).
128 */
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700129 void MarkUninitRefsAsInvalid(const RegType& uninit_type)
Ian Rogersb726dcb2012-09-05 08:57:23 -0700130 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700131
132 /*
133 * Update all registers holding "uninit_type" to instead hold the corresponding initialized
134 * reference type. This is called when an appropriate constructor is invoked -- all copies of
135 * the reference must be marked as initialized.
136 */
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800137 void MarkRefsAsInitialized(const RegType& uninit_type)
138 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700139
140 /*
Ian Rogersb8c78592013-07-25 23:52:52 +0000141 * Update all registers to be Conflict except vsrc.
142 */
143 void MarkAllRegistersAsConflicts();
144 void MarkAllRegistersAsConflictsExcept(uint32_t vsrc);
145 void MarkAllRegistersAsConflictsExceptWide(uint32_t vsrc);
146
147 /*
Ian Rogers776ac1f2012-04-13 23:36:36 -0700148 * Check constraints on constructor return. Specifically, make sure that the "this" argument got
149 * initialized.
150 * The "this" argument to <init> uses code offset kUninitThisArgAddr, which puts it at the start
151 * of the list in slot 0. If we see a register with an uninitialized slot 0 reference, we know it
152 * somehow didn't get initialized.
153 */
154 bool CheckConstructorReturn() const;
155
156 // Compare two register lines. Returns 0 if they match.
157 // Using this for a sort is unwise, since the value can change based on machine endianness.
158 int CompareLine(const RegisterLine* line2) const {
159 DCHECK(monitors_ == line2->monitors_);
160 // TODO: DCHECK(reg_to_lock_depths_ == line2->reg_to_lock_depths_);
Ian Rogersd0fbd852013-09-24 18:17:04 -0700161 return memcmp(&line_, &line2->line_, num_regs_ * sizeof(uint16_t));
Ian Rogers776ac1f2012-04-13 23:36:36 -0700162 }
163
164 size_t NumRegs() const {
165 return num_regs_;
166 }
167
168 /*
169 * Get the "this" pointer from a non-static method invocation. This returns the RegType so the
170 * caller can decide whether it needs the reference to be initialized or not. (Can also return
171 * kRegTypeZero if the reference can only be zero at this point.)
172 *
173 * The argument count is in vA, and the first argument is in vC, for both "simple" and "range"
174 * versions. We just need to make sure vA is >= 1 and then return vC.
175 */
Sebastien Hertz5243e912013-05-21 10:55:07 +0200176 const RegType& GetInvocationThis(const Instruction* inst, bool is_range)
Ian Rogersb726dcb2012-09-05 08:57:23 -0700177 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700178
179 /*
180 * Verify types for a simple two-register instruction (e.g. "neg-int").
181 * "dst_type" is stored into vA, and "src_type" is verified against vB.
182 */
Sebastien Hertz5243e912013-05-21 10:55:07 +0200183 void CheckUnaryOp(const Instruction* inst, const RegType& dst_type,
184 const RegType& src_type)
Ian Rogersb726dcb2012-09-05 08:57:23 -0700185 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700186
Sebastien Hertz5243e912013-05-21 10:55:07 +0200187 void CheckUnaryOpWide(const Instruction* inst,
Ian Rogers2bcb4a42012-11-08 10:39:18 -0800188 const RegType& dst_type1, const RegType& dst_type2,
189 const RegType& src_type1, const RegType& src_type2)
190 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
191
Sebastien Hertz5243e912013-05-21 10:55:07 +0200192 void CheckUnaryOpToWide(const Instruction* inst,
Ian Rogers2bcb4a42012-11-08 10:39:18 -0800193 const RegType& dst_type1, const RegType& dst_type2,
194 const RegType& src_type)
195 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
196
Sebastien Hertz5243e912013-05-21 10:55:07 +0200197 void CheckUnaryOpFromWide(const Instruction* inst,
Ian Rogers2bcb4a42012-11-08 10:39:18 -0800198 const RegType& dst_type,
199 const RegType& src_type1, const RegType& src_type2)
200 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
201
Ian Rogers776ac1f2012-04-13 23:36:36 -0700202 /*
203 * Verify types for a simple three-register instruction (e.g. "add-int").
204 * "dst_type" is stored into vA, and "src_type1"/"src_type2" are verified
205 * against vB/vC.
206 */
Sebastien Hertz5243e912013-05-21 10:55:07 +0200207 void CheckBinaryOp(const Instruction* inst,
Ian Rogers776ac1f2012-04-13 23:36:36 -0700208 const RegType& dst_type, const RegType& src_type1, const RegType& src_type2,
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700209 bool check_boolean_op)
Ian Rogersb726dcb2012-09-05 08:57:23 -0700210 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700211
Sebastien Hertz5243e912013-05-21 10:55:07 +0200212 void CheckBinaryOpWide(const Instruction* inst,
Ian Rogers2bcb4a42012-11-08 10:39:18 -0800213 const RegType& dst_type1, const RegType& dst_type2,
214 const RegType& src_type1_1, const RegType& src_type1_2,
215 const RegType& src_type2_1, const RegType& src_type2_2)
216 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
217
Sebastien Hertz5243e912013-05-21 10:55:07 +0200218 void CheckBinaryOpWideShift(const Instruction* inst,
Ian Rogers2bcb4a42012-11-08 10:39:18 -0800219 const RegType& long_lo_type, const RegType& long_hi_type,
220 const RegType& int_type)
221 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
222
Ian Rogers776ac1f2012-04-13 23:36:36 -0700223 /*
224 * Verify types for a binary "2addr" operation. "src_type1"/"src_type2"
225 * are verified against vA/vB, then "dst_type" is stored into vA.
226 */
Sebastien Hertz5243e912013-05-21 10:55:07 +0200227 void CheckBinaryOp2addr(const Instruction* inst,
Ian Rogers776ac1f2012-04-13 23:36:36 -0700228 const RegType& dst_type,
229 const RegType& src_type1, const RegType& src_type2,
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700230 bool check_boolean_op)
Ian Rogersb726dcb2012-09-05 08:57:23 -0700231 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700232
Sebastien Hertz5243e912013-05-21 10:55:07 +0200233 void CheckBinaryOp2addrWide(const Instruction* inst,
Ian Rogers2bcb4a42012-11-08 10:39:18 -0800234 const RegType& dst_type1, const RegType& dst_type2,
235 const RegType& src_type1_1, const RegType& src_type1_2,
236 const RegType& src_type2_1, const RegType& src_type2_2)
237 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
238
Sebastien Hertz5243e912013-05-21 10:55:07 +0200239 void CheckBinaryOp2addrWideShift(const Instruction* inst,
Ian Rogers2bcb4a42012-11-08 10:39:18 -0800240 const RegType& long_lo_type, const RegType& long_hi_type,
241 const RegType& int_type)
242 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
243
Ian Rogers776ac1f2012-04-13 23:36:36 -0700244 /*
245 * Verify types for A two-register instruction with a literal constant (e.g. "add-int/lit8").
246 * "dst_type" is stored into vA, and "src_type" is verified against vB.
247 *
248 * If "check_boolean_op" is set, we use the constant value in vC.
249 */
Sebastien Hertz5243e912013-05-21 10:55:07 +0200250 void CheckLiteralOp(const Instruction* inst,
251 const RegType& dst_type, const RegType& src_type,
252 bool check_boolean_op, bool is_lit16)
Ian Rogersb726dcb2012-09-05 08:57:23 -0700253 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700254
255 // Verify/push monitor onto the monitor stack, locking the value in reg_idx at location insn_idx.
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800256 void PushMonitor(uint32_t reg_idx, int32_t insn_idx) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700257
258 // Verify/pop monitor from monitor stack ensuring that we believe the monitor is locked
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800259 void PopMonitor(uint32_t reg_idx) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700260
261 // Stack of currently held monitors and where they were locked
262 size_t MonitorStackDepth() const {
263 return monitors_.size();
264 }
265
266 // We expect no monitors to be held at certain points, such a method returns. Verify the stack
267 // is empty, failing and returning false if not.
Jeff Hao673b6832013-07-31 13:47:31 -0700268 bool VerifyMonitorStackEmpty() const;
Ian Rogers776ac1f2012-04-13 23:36:36 -0700269
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700270 bool MergeRegisters(const RegisterLine* incoming_line)
Ian Rogersb726dcb2012-09-05 08:57:23 -0700271 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700272
273 size_t GetMaxNonZeroReferenceReg(size_t max_ref_reg) {
274 size_t i = static_cast<int>(max_ref_reg) < 0 ? 0 : max_ref_reg;
275 for (; i < num_regs_; i++) {
276 if (GetRegisterType(i).IsNonZeroReferenceTypes()) {
277 max_ref_reg = i;
278 }
279 }
280 return max_ref_reg;
281 }
282
283 // Write a bit at each register location that holds a reference
284 void WriteReferenceBitMap(std::vector<uint8_t>& data, size_t max_bytes);
Ian Rogers776ac1f2012-04-13 23:36:36 -0700285
Elliott Hughes08fc03a2012-06-26 17:34:00 -0700286 size_t GetMonitorEnterCount() {
287 return monitors_.size();
288 }
289
290 uint32_t GetMonitorEnterDexPc(size_t i) {
291 return monitors_[i];
292 }
293
Elliott Hughesa21039c2012-06-21 12:09:25 -0700294 private:
Ian Rogers776ac1f2012-04-13 23:36:36 -0700295 void CopyRegToLockDepth(size_t dst, size_t src) {
296 SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(src);
297 if (it != reg_to_lock_depths_.end()) {
298 reg_to_lock_depths_.Put(dst, it->second);
299 }
300 }
301
302 bool IsSetLockDepth(size_t reg, size_t depth) {
303 SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg);
304 if (it != reg_to_lock_depths_.end()) {
305 return (it->second & (1 << depth)) != 0;
306 } else {
307 return false;
308 }
309 }
310
311 void SetRegToLockDepth(size_t reg, size_t depth) {
312 CHECK_LT(depth, 32u);
313 DCHECK(!IsSetLockDepth(reg, depth));
314 SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg);
315 if (it == reg_to_lock_depths_.end()) {
316 reg_to_lock_depths_.Put(reg, 1 << depth);
317 } else {
318 it->second |= (1 << depth);
319 }
320 }
321
322 void ClearRegToLockDepth(size_t reg, size_t depth) {
323 CHECK_LT(depth, 32u);
324 DCHECK(IsSetLockDepth(reg, depth));
325 SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg);
326 DCHECK(it != reg_to_lock_depths_.end());
327 uint32_t depths = it->second ^ (1 << depth);
328 if (depths != 0) {
329 it->second = depths;
330 } else {
331 reg_to_lock_depths_.erase(it);
332 }
333 }
334
335 void ClearAllRegToLockDepths(size_t reg) {
336 reg_to_lock_depths_.erase(reg);
337 }
338
Ian Rogersd0fbd852013-09-24 18:17:04 -0700339 RegisterLine(size_t num_regs, MethodVerifier* verifier)
340 : verifier_(verifier),
341 num_regs_(num_regs) {
342 memset(&line_, 0, num_regs_ * sizeof(uint16_t));
343 SetResultTypeToUnknown();
344 }
345
Ian Rogers776ac1f2012-04-13 23:36:36 -0700346 // Storage for the result register's type, valid after an invocation
347 uint16_t result_[2];
348
Ian Rogers776ac1f2012-04-13 23:36:36 -0700349 // Back link to the verifier
350 MethodVerifier* verifier_;
351
352 // Length of reg_types_
Ian Rogersad0b3a32012-04-16 14:50:24 -0700353 const uint32_t num_regs_;
Ian Rogers776ac1f2012-04-13 23:36:36 -0700354 // A stack of monitor enter locations
Ian Rogersd0fbd852013-09-24 18:17:04 -0700355 std::vector<uint32_t> monitors_;
Ian Rogers776ac1f2012-04-13 23:36:36 -0700356 // A map from register to a bit vector of indices into the monitors_ stack. As we pop the monitor
357 // stack we verify that monitor-enter/exit are correctly nested. That is, if there was a
358 // monitor-enter on v5 and then on v6, we expect the monitor-exit to be on v6 then on v5
359 SafeMap<uint32_t, uint32_t> reg_to_lock_depths_;
Ian Rogersd0fbd852013-09-24 18:17:04 -0700360
361 // An array of RegType Ids associated with each dex register.
362 uint16_t line_[0];
Ian Rogers776ac1f2012-04-13 23:36:36 -0700363};
364std::ostream& operator<<(std::ostream& os, const RegisterLine& rhs);
365
366} // namespace verifier
367} // namespace art
368
Brian Carlstromfc0e3212013-07-17 14:40:12 -0700369#endif // ART_RUNTIME_VERIFIER_REGISTER_LINE_H_