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