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