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 25 namespace art { 26 27 class Instruction; 28 29 namespace verifier { 30 31 class MethodVerifier; 32 class 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 */ 43 enum 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). 53 class RegisterLine { 54 public: Create(size_t num_regs,MethodVerifier * verifier)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 CopyFromLine(const RegisterLine * src)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 FillWithGarbage()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 SetThisInitialized()153 void SetThisInitialized() { 154 this_initialized_ = true; 155 } 156 CopyThisInitialized(const RegisterLine & src)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. CompareLine(const RegisterLine * line2)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 NumRegs()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 MonitorStackDepth()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 GetMonitorEnterCount()297 size_t GetMonitorEnterCount() { 298 return monitors_.size(); 299 } 300 GetMonitorEnterDexPc(size_t i)301 uint32_t GetMonitorEnterDexPc(size_t i) { 302 return monitors_[i]; 303 } 304 305 private: CopyRegToLockDepth(size_t dst,size_t src)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 IsSetLockDepth(size_t reg,size_t depth)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 SetRegToLockDepth(size_t reg,size_t depth)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 ClearRegToLockDepth(size_t reg,size_t depth)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 ClearAllRegToLockDepths(size_t reg)349 void ClearAllRegToLockDepths(size_t reg) { 350 reg_to_lock_depths_.erase(reg); 351 } 352 RegisterLine(size_t num_regs,MethodVerifier * verifier)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