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 REQUIRES_SHARED(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 REQUIRES_SHARED(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 REQUIRES_SHARED(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 REQUIRES_SHARED(Locks::mutator_lock_); 86 87 // Set the invisible result register to unknown 88 void SetResultTypeToUnknown(MethodVerifier* verifier) REQUIRES_SHARED(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 REQUIRES_SHARED(Locks::mutator_lock_); 106 107 bool SetRegisterTypeWide(MethodVerifier* verifier, 108 uint32_t vdst, 109 const RegType& new_type1, 110 const RegType& new_type2) 111 REQUIRES_SHARED(Locks::mutator_lock_); 112 113 /* Set the type of the "result" register. */ 114 void SetResultRegisterType(MethodVerifier* verifier, const RegType& new_type) 115 REQUIRES_SHARED(Locks::mutator_lock_); 116 117 void SetResultRegisterTypeWide(const RegType& new_type1, const RegType& new_type2) 118 REQUIRES_SHARED(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 REQUIRES_SHARED(Locks::mutator_lock_); 127 128 bool VerifyRegisterTypeWide(MethodVerifier* verifier, 129 uint32_t vsrc, 130 const RegType& check_type1, 131 const RegType& check_type2) 132 REQUIRES_SHARED(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 REQUIRES_SHARED(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 REQUIRES_SHARED(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 REQUIRES_SHARED(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 allow_failure = false) 221 REQUIRES_SHARED(Locks::mutator_lock_); 222 223 /* 224 * Verify types for a simple two-register instruction (e.g. "neg-int"). 225 * "dst_type" is stored into vA, and "src_type" is verified against vB. 226 */ 227 void CheckUnaryOp(MethodVerifier* verifier, 228 const Instruction* inst, 229 const RegType& dst_type, 230 const RegType& src_type) 231 REQUIRES_SHARED(Locks::mutator_lock_); 232 233 void CheckUnaryOpWide(MethodVerifier* verifier, 234 const Instruction* inst, 235 const RegType& dst_type1, 236 const RegType& dst_type2, 237 const RegType& src_type1, 238 const RegType& src_type2) 239 REQUIRES_SHARED(Locks::mutator_lock_); 240 241 void CheckUnaryOpToWide(MethodVerifier* verifier, 242 const Instruction* inst, 243 const RegType& dst_type1, 244 const RegType& dst_type2, 245 const RegType& src_type) 246 REQUIRES_SHARED(Locks::mutator_lock_); 247 248 void CheckUnaryOpFromWide(MethodVerifier* verifier, 249 const Instruction* inst, 250 const RegType& dst_type, 251 const RegType& src_type1, 252 const RegType& src_type2) 253 REQUIRES_SHARED(Locks::mutator_lock_); 254 255 /* 256 * Verify types for a simple three-register instruction (e.g. "add-int"). 257 * "dst_type" is stored into vA, and "src_type1"/"src_type2" are verified 258 * against vB/vC. 259 */ 260 void CheckBinaryOp(MethodVerifier* verifier, 261 const Instruction* inst, 262 const RegType& dst_type, 263 const RegType& src_type1, 264 const RegType& src_type2, 265 bool check_boolean_op) 266 REQUIRES_SHARED(Locks::mutator_lock_); 267 268 void CheckBinaryOpWide(MethodVerifier* verifier, 269 const Instruction* inst, 270 const RegType& dst_type1, 271 const RegType& dst_type2, 272 const RegType& src_type1_1, 273 const RegType& src_type1_2, 274 const RegType& src_type2_1, 275 const RegType& src_type2_2) 276 REQUIRES_SHARED(Locks::mutator_lock_); 277 278 void CheckBinaryOpWideShift(MethodVerifier* verifier, 279 const Instruction* inst, 280 const RegType& long_lo_type, 281 const RegType& long_hi_type, 282 const RegType& int_type) 283 REQUIRES_SHARED(Locks::mutator_lock_); 284 285 /* 286 * Verify types for a binary "2addr" operation. "src_type1"/"src_type2" 287 * are verified against vA/vB, then "dst_type" is stored into vA. 288 */ 289 void CheckBinaryOp2addr(MethodVerifier* verifier, 290 const Instruction* inst, 291 const RegType& dst_type, 292 const RegType& src_type1, 293 const RegType& src_type2, 294 bool check_boolean_op) 295 REQUIRES_SHARED(Locks::mutator_lock_); 296 297 void CheckBinaryOp2addrWide(MethodVerifier* verifier, 298 const Instruction* inst, 299 const RegType& dst_type1, 300 const RegType& dst_type2, 301 const RegType& src_type1_1, 302 const RegType& src_type1_2, 303 const RegType& src_type2_1, 304 const RegType& src_type2_2) 305 REQUIRES_SHARED(Locks::mutator_lock_); 306 307 void CheckBinaryOp2addrWideShift(MethodVerifier* verifier, 308 const Instruction* inst, 309 const RegType& long_lo_type, 310 const RegType& long_hi_type, 311 const RegType& int_type) 312 REQUIRES_SHARED(Locks::mutator_lock_); 313 314 /* 315 * Verify types for A two-register instruction with a literal constant (e.g. "add-int/lit8"). 316 * "dst_type" is stored into vA, and "src_type" is verified against vB. 317 * 318 * If "check_boolean_op" is set, we use the constant value in vC. 319 */ 320 void CheckLiteralOp(MethodVerifier* verifier, 321 const Instruction* inst, 322 const RegType& dst_type, 323 const RegType& src_type, 324 bool check_boolean_op, 325 bool is_lit16) 326 REQUIRES_SHARED(Locks::mutator_lock_); 327 328 // Verify/push monitor onto the monitor stack, locking the value in reg_idx at location insn_idx. 329 void PushMonitor(MethodVerifier* verifier, uint32_t reg_idx, int32_t insn_idx) 330 REQUIRES_SHARED(Locks::mutator_lock_); 331 332 // Verify/pop monitor from monitor stack ensuring that we believe the monitor is locked 333 void PopMonitor(MethodVerifier* verifier, uint32_t reg_idx) 334 REQUIRES_SHARED(Locks::mutator_lock_); 335 336 // Stack of currently held monitors and where they were locked MonitorStackDepth()337 size_t MonitorStackDepth() const { 338 return monitors_.size(); 339 } 340 341 // We expect no monitors to be held at certain points, such a method returns. Verify the stack 342 // is empty, queueing a LOCKING error else. 343 void VerifyMonitorStackEmpty(MethodVerifier* verifier) const; 344 345 bool MergeRegisters(MethodVerifier* verifier, const RegisterLine* incoming_line) 346 REQUIRES_SHARED(Locks::mutator_lock_); 347 GetMonitorEnterCount()348 size_t GetMonitorEnterCount() const { 349 return monitors_.size(); 350 } 351 GetMonitorEnterDexPc(size_t i)352 uint32_t GetMonitorEnterDexPc(size_t i) const { 353 return monitors_[i]; 354 } 355 356 private: CopyRegToLockDepth(size_t dst,size_t src)357 void CopyRegToLockDepth(size_t dst, size_t src) { 358 auto it = reg_to_lock_depths_.find(src); 359 if (it != reg_to_lock_depths_.end()) { 360 reg_to_lock_depths_.Put(dst, it->second); 361 } 362 } 363 IsSetLockDepth(size_t reg,size_t depth)364 bool IsSetLockDepth(size_t reg, size_t depth) { 365 auto it = reg_to_lock_depths_.find(reg); 366 if (it != reg_to_lock_depths_.end()) { 367 return (it->second & (1 << depth)) != 0; 368 } else { 369 return false; 370 } 371 } 372 SetRegToLockDepth(size_t reg,size_t depth)373 bool SetRegToLockDepth(size_t reg, size_t depth) { 374 CHECK_LT(depth, 32u); 375 if (IsSetLockDepth(reg, depth)) { 376 return false; // Register already holds lock so locking twice is erroneous. 377 } 378 auto it = reg_to_lock_depths_.find(reg); 379 if (it == reg_to_lock_depths_.end()) { 380 reg_to_lock_depths_.Put(reg, 1 << depth); 381 } else { 382 it->second |= (1 << depth); 383 } 384 return true; 385 } 386 ClearRegToLockDepth(size_t reg,size_t depth)387 void ClearRegToLockDepth(size_t reg, size_t depth) { 388 CHECK_LT(depth, 32u); 389 DCHECK(IsSetLockDepth(reg, depth)); 390 auto it = reg_to_lock_depths_.find(reg); 391 DCHECK(it != reg_to_lock_depths_.end()); 392 uint32_t depths = it->second ^ (1 << depth); 393 if (depths != 0) { 394 it->second = depths; 395 } else { 396 reg_to_lock_depths_.erase(it); 397 } 398 // Need to unlock every register at the same lock depth. These are aliased locks. 399 uint32_t mask = 1 << depth; 400 for (auto& pair : reg_to_lock_depths_) { 401 if ((pair.second & mask) != 0) { 402 VLOG(verifier) << "Also unlocking " << pair.first; 403 pair.second ^= mask; 404 } 405 } 406 } 407 ClearAllRegToLockDepths(size_t reg)408 void ClearAllRegToLockDepths(size_t reg) { 409 reg_to_lock_depths_.erase(reg); 410 } 411 412 RegisterLine(size_t num_regs, MethodVerifier* verifier); 413 414 // Storage for the result register's type, valid after an invocation. 415 uint16_t result_[2]; 416 417 // Length of reg_types_ 418 const uint32_t num_regs_; 419 420 // A stack of monitor enter locations. 421 ScopedArenaVector<uint32_t> monitors_; 422 423 // A map from register to a bit vector of indices into the monitors_ stack. As we pop the monitor 424 // stack we verify that monitor-enter/exit are correctly nested. That is, if there was a 425 // monitor-enter on v5 and then on v6, we expect the monitor-exit to be on v6 then on v5. 426 RegToLockDepthsMap reg_to_lock_depths_; 427 428 // Whether "this" initialization (a constructor supercall) has happened. 429 bool this_initialized_; 430 431 // An array of RegType Ids associated with each dex register. 432 uint16_t line_[1]; 433 434 DISALLOW_COPY_AND_ASSIGN(RegisterLine); 435 }; 436 437 class RegisterLineArenaDelete : public ArenaDelete<RegisterLine> { 438 public: 439 void operator()(RegisterLine* ptr) const; 440 }; 441 442 } // namespace verifier 443 } // namespace art 444 445 #endif // ART_RUNTIME_VERIFIER_REGISTER_LINE_H_ 446