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