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 "dex_instruction.h" 24 #include "reg_type.h" 25 #include "safe_map.h" 26 27 namespace art { 28 namespace verifier { 29 30 class 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 */ 41 enum 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). 51 class RegisterLine { 52 public: Create(size_t num_regs,MethodVerifier * verifier)53 static RegisterLine* Create(size_t num_regs, MethodVerifier* verifier) { 54 void* memory = operator new(sizeof(RegisterLine) + (num_regs * sizeof(uint16_t))); 55 RegisterLine* rl = new (memory) RegisterLine(num_regs, verifier); 56 return rl; 57 } 58 59 // Implement category-1 "move" instructions. Copy a 32-bit value from "vsrc" to "vdst". 60 void CopyRegister1(uint32_t vdst, uint32_t vsrc, TypeCategory cat) 61 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 62 63 // Implement category-2 "move" instructions. Copy a 64-bit value from "vsrc" to "vdst". This 64 // copies both halves of the register. 65 void CopyRegister2(uint32_t vdst, uint32_t vsrc) 66 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 67 68 // Implement "move-result". Copy the category-1 value from the result register to another 69 // register, and reset the result register. 70 void CopyResultRegister1(uint32_t vdst, bool is_reference) 71 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 72 73 // Implement "move-result-wide". Copy the category-2 value from the result register to another 74 // register, and reset the result register. 75 void CopyResultRegister2(uint32_t vdst) 76 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 77 78 // Set the invisible result register to unknown 79 void SetResultTypeToUnknown() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 80 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. 84 bool SetRegisterType(uint32_t vdst, RegType& new_type) 85 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 86 87 bool SetRegisterTypeWide(uint32_t vdst, RegType& new_type1, RegType& new_type2) 88 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 89 90 /* Set the type of the "result" register. */ 91 void SetResultRegisterType(RegType& new_type) 92 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 93 94 void SetResultRegisterTypeWide(RegType& new_type1, RegType& new_type2) 95 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 96 97 // Get the type of register vsrc. 98 RegType& GetRegisterType(uint32_t vsrc) const; 99 100 bool VerifyRegisterType(uint32_t vsrc, RegType& check_type) 101 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 102 103 bool VerifyRegisterTypeWide(uint32_t vsrc, RegType& check_type1, RegType& check_type2) 104 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 105 CopyFromLine(const RegisterLine * src)106 void CopyFromLine(const RegisterLine* src) { 107 DCHECK_EQ(num_regs_, src->num_regs_); 108 memcpy(&line_, &src->line_, num_regs_ * sizeof(uint16_t)); 109 monitors_ = src->monitors_; 110 reg_to_lock_depths_ = src->reg_to_lock_depths_; 111 } 112 113 std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 114 FillWithGarbage()115 void FillWithGarbage() { 116 memset(&line_, 0xf1, num_regs_ * sizeof(uint16_t)); 117 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 */ 129 void MarkUninitRefsAsInvalid(RegType& uninit_type) 130 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 131 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 */ 137 void MarkRefsAsInitialized(RegType& uninit_type) 138 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 139 140 /* 141 * 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 /* 148 * 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. CompareLine(const RegisterLine * line2)158 int CompareLine(const RegisterLine* line2) const { 159 DCHECK(monitors_ == line2->monitors_); 160 // TODO: DCHECK(reg_to_lock_depths_ == line2->reg_to_lock_depths_); 161 return memcmp(&line_, &line2->line_, num_regs_ * sizeof(uint16_t)); 162 } 163 NumRegs()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 */ 176 RegType& GetInvocationThis(const Instruction* inst, bool is_range) 177 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 178 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 */ 183 void CheckUnaryOp(const Instruction* inst, RegType& dst_type, 184 RegType& src_type) 185 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 186 187 void CheckUnaryOpWide(const Instruction* inst, 188 RegType& dst_type1, RegType& dst_type2, 189 RegType& src_type1, RegType& src_type2) 190 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 191 192 void CheckUnaryOpToWide(const Instruction* inst, 193 RegType& dst_type1, RegType& dst_type2, 194 RegType& src_type) 195 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 196 197 void CheckUnaryOpFromWide(const Instruction* inst, 198 RegType& dst_type, 199 RegType& src_type1, RegType& src_type2) 200 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 201 202 /* 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 */ 207 void CheckBinaryOp(const Instruction* inst, 208 RegType& dst_type, RegType& src_type1, RegType& src_type2, 209 bool check_boolean_op) 210 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 211 212 void CheckBinaryOpWide(const Instruction* inst, 213 RegType& dst_type1, RegType& dst_type2, 214 RegType& src_type1_1, RegType& src_type1_2, 215 RegType& src_type2_1, RegType& src_type2_2) 216 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 217 218 void CheckBinaryOpWideShift(const Instruction* inst, 219 RegType& long_lo_type, RegType& long_hi_type, 220 RegType& int_type) 221 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 222 223 /* 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 */ 227 void CheckBinaryOp2addr(const Instruction* inst, 228 RegType& dst_type, 229 RegType& src_type1, RegType& src_type2, 230 bool check_boolean_op) 231 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 232 233 void CheckBinaryOp2addrWide(const Instruction* inst, 234 RegType& dst_type1, RegType& dst_type2, 235 RegType& src_type1_1, RegType& src_type1_2, 236 RegType& src_type2_1, RegType& src_type2_2) 237 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 238 239 void CheckBinaryOp2addrWideShift(const Instruction* inst, 240 RegType& long_lo_type, RegType& long_hi_type, 241 RegType& int_type) 242 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 243 244 /* 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 */ 250 void CheckLiteralOp(const Instruction* inst, 251 RegType& dst_type, RegType& src_type, 252 bool check_boolean_op, bool is_lit16) 253 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 254 255 // Verify/push monitor onto the monitor stack, locking the value in reg_idx at location insn_idx. 256 void PushMonitor(uint32_t reg_idx, int32_t insn_idx) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 257 258 // Verify/pop monitor from monitor stack ensuring that we believe the monitor is locked 259 void PopMonitor(uint32_t reg_idx) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 260 261 // Stack of currently held monitors and where they were locked MonitorStackDepth()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. 268 bool VerifyMonitorStackEmpty() const; 269 270 bool MergeRegisters(const RegisterLine* incoming_line) 271 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 272 GetMaxNonZeroReferenceReg(size_t max_ref_reg)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); 285 GetMonitorEnterCount()286 size_t GetMonitorEnterCount() { 287 return monitors_.size(); 288 } 289 GetMonitorEnterDexPc(size_t i)290 uint32_t GetMonitorEnterDexPc(size_t i) { 291 return monitors_[i]; 292 } 293 294 private: CopyRegToLockDepth(size_t dst,size_t src)295 void CopyRegToLockDepth(size_t dst, size_t src) { 296 auto 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 IsSetLockDepth(size_t reg,size_t depth)302 bool IsSetLockDepth(size_t reg, size_t depth) { 303 auto 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 SetRegToLockDepth(size_t reg,size_t depth)311 void SetRegToLockDepth(size_t reg, size_t depth) { 312 CHECK_LT(depth, 32u); 313 DCHECK(!IsSetLockDepth(reg, depth)); 314 auto 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 ClearRegToLockDepth(size_t reg,size_t depth)322 void ClearRegToLockDepth(size_t reg, size_t depth) { 323 CHECK_LT(depth, 32u); 324 DCHECK(IsSetLockDepth(reg, depth)); 325 auto 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 ClearAllRegToLockDepths(size_t reg)335 void ClearAllRegToLockDepths(size_t reg) { 336 reg_to_lock_depths_.erase(reg); 337 } 338 RegisterLine(size_t num_regs,MethodVerifier * verifier)339 RegisterLine(size_t num_regs, MethodVerifier* verifier) 340 : verifier_(verifier), num_regs_(num_regs) { 341 memset(&line_, 0, num_regs_ * sizeof(uint16_t)); 342 SetResultTypeToUnknown(); 343 } 344 345 // Storage for the result register's type, valid after an invocation 346 uint16_t result_[2]; 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::vector<uint32_t, TrackingAllocator<uint32_t, kAllocatorTagVerifier>> 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 AllocationTrackingSafeMap<uint32_t, uint32_t, kAllocatorTagVerifier> reg_to_lock_depths_; 359 360 // An array of RegType Ids associated with each dex register. 361 uint16_t line_[0]; 362 }; 363 std::ostream& operator<<(std::ostream& os, const RegisterLine& rhs); 364 365 } // namespace verifier 366 } // namespace art 367 368 #endif // ART_RUNTIME_VERIFIER_REGISTER_LINE_H_ 369