Ian Rogers | 776ac1f | 2012-04-13 23:36:36 -0700 | [diff] [blame] | 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_SRC_VERIFIER_REGISTER_LINE_H_ |
| 18 | #define ART_SRC_VERIFIER_REGISTER_LINE_H_ |
| 19 | |
| 20 | #include <deque> |
| 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 | // If live-precise register maps are enabled, the "liveRegs" vector will be populated. Unlike the |
| 52 | // other lists of registers here, we do not track the liveness of the method result register |
| 53 | // (which is not visible to the GC). |
| 54 | class RegisterLine { |
| 55 | public: |
| 56 | RegisterLine(size_t num_regs, MethodVerifier* verifier) : |
| 57 | line_(new uint16_t[num_regs]), verifier_(verifier), num_regs_(num_regs) { |
| 58 | memset(line_.get(), 0, num_regs_ * sizeof(uint16_t)); |
Ian Rogers | ad0b3a3 | 2012-04-16 14:50:24 -0700 | [diff] [blame] | 59 | result_[0] = RegType::kRegTypeUndefined; |
| 60 | result_[1] = RegType::kRegTypeUndefined; |
Ian Rogers | 776ac1f | 2012-04-13 23:36:36 -0700 | [diff] [blame] | 61 | } |
| 62 | |
| 63 | // Implement category-1 "move" instructions. Copy a 32-bit value from "vsrc" to "vdst". |
| 64 | void CopyRegister1(uint32_t vdst, uint32_t vsrc, TypeCategory cat); |
| 65 | |
| 66 | // Implement category-2 "move" instructions. Copy a 64-bit value from "vsrc" to "vdst". This |
| 67 | // copies both halves of the register. |
| 68 | void CopyRegister2(uint32_t vdst, uint32_t vsrc); |
| 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(uint32_t vdst, bool is_reference); |
| 73 | |
| 74 | // Implement "move-result-wide". Copy the category-2 value from the result register to another |
| 75 | // register, and reset the result register. |
| 76 | void CopyResultRegister2(uint32_t vdst); |
| 77 | |
| 78 | // Set the invisible result register to unknown |
| 79 | void SetResultTypeToUnknown(); |
| 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, const RegType& new_type); |
| 85 | |
| 86 | /* Set the type of the "result" register. */ |
| 87 | void SetResultRegisterType(const RegType& new_type); |
| 88 | |
| 89 | // Get the type of register vsrc. |
| 90 | const RegType& GetRegisterType(uint32_t vsrc) const; |
| 91 | |
| 92 | bool VerifyRegisterType(uint32_t vsrc, const RegType& check_type); |
| 93 | |
| 94 | void CopyFromLine(const RegisterLine* src) { |
| 95 | DCHECK_EQ(num_regs_, src->num_regs_); |
| 96 | memcpy(line_.get(), src->line_.get(), num_regs_ * sizeof(uint16_t)); |
| 97 | monitors_ = src->monitors_; |
| 98 | reg_to_lock_depths_ = src->reg_to_lock_depths_; |
| 99 | } |
| 100 | |
| 101 | std::string Dump() const { |
| 102 | std::string result; |
| 103 | for (size_t i = 0; i < num_regs_; i++) { |
| 104 | result += StringPrintf("%zd:[", i); |
| 105 | result += GetRegisterType(i).Dump(); |
| 106 | result += "],"; |
| 107 | } |
| 108 | typedef std::deque<uint32_t>::const_iterator It; // TODO: C++0x auto |
| 109 | for (It it = monitors_.begin(), end = monitors_.end(); it != end ; ++it) { |
| 110 | result += StringPrintf("{%d},", *it); |
| 111 | } |
| 112 | return result; |
| 113 | } |
| 114 | |
| 115 | void FillWithGarbage() { |
| 116 | memset(line_.get(), 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(const RegType& uninit_type); |
| 130 | |
| 131 | /* |
| 132 | * Update all registers holding "uninit_type" to instead hold the corresponding initialized |
| 133 | * reference type. This is called when an appropriate constructor is invoked -- all copies of |
| 134 | * the reference must be marked as initialized. |
| 135 | */ |
| 136 | void MarkRefsAsInitialized(const RegType& uninit_type); |
| 137 | |
| 138 | /* |
| 139 | * Check constraints on constructor return. Specifically, make sure that the "this" argument got |
| 140 | * initialized. |
| 141 | * The "this" argument to <init> uses code offset kUninitThisArgAddr, which puts it at the start |
| 142 | * of the list in slot 0. If we see a register with an uninitialized slot 0 reference, we know it |
| 143 | * somehow didn't get initialized. |
| 144 | */ |
| 145 | bool CheckConstructorReturn() const; |
| 146 | |
| 147 | // Compare two register lines. Returns 0 if they match. |
| 148 | // Using this for a sort is unwise, since the value can change based on machine endianness. |
| 149 | int CompareLine(const RegisterLine* line2) const { |
| 150 | DCHECK(monitors_ == line2->monitors_); |
| 151 | // TODO: DCHECK(reg_to_lock_depths_ == line2->reg_to_lock_depths_); |
| 152 | return memcmp(line_.get(), line2->line_.get(), num_regs_ * sizeof(uint16_t)); |
| 153 | } |
| 154 | |
| 155 | size_t NumRegs() const { |
| 156 | return num_regs_; |
| 157 | } |
| 158 | |
| 159 | /* |
| 160 | * Get the "this" pointer from a non-static method invocation. This returns the RegType so the |
| 161 | * caller can decide whether it needs the reference to be initialized or not. (Can also return |
| 162 | * kRegTypeZero if the reference can only be zero at this point.) |
| 163 | * |
| 164 | * The argument count is in vA, and the first argument is in vC, for both "simple" and "range" |
| 165 | * versions. We just need to make sure vA is >= 1 and then return vC. |
| 166 | */ |
| 167 | const RegType& GetInvocationThis(const DecodedInstruction& dec_insn); |
| 168 | |
| 169 | /* |
| 170 | * Verify types for a simple two-register instruction (e.g. "neg-int"). |
| 171 | * "dst_type" is stored into vA, and "src_type" is verified against vB. |
| 172 | */ |
| 173 | void CheckUnaryOp(const DecodedInstruction& dec_insn, |
| 174 | const RegType& dst_type, const RegType& src_type); |
| 175 | |
| 176 | /* |
| 177 | * Verify types for a simple three-register instruction (e.g. "add-int"). |
| 178 | * "dst_type" is stored into vA, and "src_type1"/"src_type2" are verified |
| 179 | * against vB/vC. |
| 180 | */ |
| 181 | void CheckBinaryOp(const DecodedInstruction& dec_insn, |
| 182 | const RegType& dst_type, const RegType& src_type1, const RegType& src_type2, |
| 183 | bool check_boolean_op); |
| 184 | |
| 185 | /* |
| 186 | * Verify types for a binary "2addr" operation. "src_type1"/"src_type2" |
| 187 | * are verified against vA/vB, then "dst_type" is stored into vA. |
| 188 | */ |
| 189 | void CheckBinaryOp2addr(const DecodedInstruction& dec_insn, |
| 190 | const RegType& dst_type, |
| 191 | const RegType& src_type1, const RegType& src_type2, |
| 192 | bool check_boolean_op); |
| 193 | |
| 194 | /* |
| 195 | * Verify types for A two-register instruction with a literal constant (e.g. "add-int/lit8"). |
| 196 | * "dst_type" is stored into vA, and "src_type" is verified against vB. |
| 197 | * |
| 198 | * If "check_boolean_op" is set, we use the constant value in vC. |
| 199 | */ |
| 200 | void CheckLiteralOp(const DecodedInstruction& dec_insn, |
| 201 | const RegType& dst_type, const RegType& src_type, bool check_boolean_op); |
| 202 | |
| 203 | // Verify/push monitor onto the monitor stack, locking the value in reg_idx at location insn_idx. |
| 204 | void PushMonitor(uint32_t reg_idx, int32_t insn_idx); |
| 205 | |
| 206 | // Verify/pop monitor from monitor stack ensuring that we believe the monitor is locked |
| 207 | void PopMonitor(uint32_t reg_idx); |
| 208 | |
| 209 | // Stack of currently held monitors and where they were locked |
| 210 | size_t MonitorStackDepth() const { |
| 211 | return monitors_.size(); |
| 212 | } |
| 213 | |
| 214 | // We expect no monitors to be held at certain points, such a method returns. Verify the stack |
| 215 | // is empty, failing and returning false if not. |
| 216 | bool VerifyMonitorStackEmpty(); |
| 217 | |
| 218 | bool MergeRegisters(const RegisterLine* incoming_line); |
| 219 | |
| 220 | size_t GetMaxNonZeroReferenceReg(size_t max_ref_reg) { |
| 221 | size_t i = static_cast<int>(max_ref_reg) < 0 ? 0 : max_ref_reg; |
| 222 | for (; i < num_regs_; i++) { |
| 223 | if (GetRegisterType(i).IsNonZeroReferenceTypes()) { |
| 224 | max_ref_reg = i; |
| 225 | } |
| 226 | } |
| 227 | return max_ref_reg; |
| 228 | } |
| 229 | |
| 230 | // Write a bit at each register location that holds a reference |
| 231 | void WriteReferenceBitMap(std::vector<uint8_t>& data, size_t max_bytes); |
Ian Rogers | 776ac1f | 2012-04-13 23:36:36 -0700 | [diff] [blame] | 232 | |
Elliott Hughes | a21039c | 2012-06-21 12:09:25 -0700 | [diff] [blame^] | 233 | private: |
Ian Rogers | 776ac1f | 2012-04-13 23:36:36 -0700 | [diff] [blame] | 234 | void CopyRegToLockDepth(size_t dst, size_t src) { |
| 235 | SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(src); |
| 236 | if (it != reg_to_lock_depths_.end()) { |
| 237 | reg_to_lock_depths_.Put(dst, it->second); |
| 238 | } |
| 239 | } |
| 240 | |
| 241 | bool IsSetLockDepth(size_t reg, size_t depth) { |
| 242 | SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg); |
| 243 | if (it != reg_to_lock_depths_.end()) { |
| 244 | return (it->second & (1 << depth)) != 0; |
| 245 | } else { |
| 246 | return false; |
| 247 | } |
| 248 | } |
| 249 | |
| 250 | void SetRegToLockDepth(size_t reg, size_t depth) { |
| 251 | CHECK_LT(depth, 32u); |
| 252 | DCHECK(!IsSetLockDepth(reg, depth)); |
| 253 | SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg); |
| 254 | if (it == reg_to_lock_depths_.end()) { |
| 255 | reg_to_lock_depths_.Put(reg, 1 << depth); |
| 256 | } else { |
| 257 | it->second |= (1 << depth); |
| 258 | } |
| 259 | } |
| 260 | |
| 261 | void ClearRegToLockDepth(size_t reg, size_t depth) { |
| 262 | CHECK_LT(depth, 32u); |
| 263 | DCHECK(IsSetLockDepth(reg, depth)); |
| 264 | SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg); |
| 265 | DCHECK(it != reg_to_lock_depths_.end()); |
| 266 | uint32_t depths = it->second ^ (1 << depth); |
| 267 | if (depths != 0) { |
| 268 | it->second = depths; |
| 269 | } else { |
| 270 | reg_to_lock_depths_.erase(it); |
| 271 | } |
| 272 | } |
| 273 | |
| 274 | void ClearAllRegToLockDepths(size_t reg) { |
| 275 | reg_to_lock_depths_.erase(reg); |
| 276 | } |
| 277 | |
| 278 | // Storage for the result register's type, valid after an invocation |
| 279 | uint16_t result_[2]; |
| 280 | |
| 281 | // An array of RegType Ids associated with each dex register |
| 282 | UniquePtr<uint16_t[]> line_; |
| 283 | |
| 284 | // Back link to the verifier |
| 285 | MethodVerifier* verifier_; |
| 286 | |
| 287 | // Length of reg_types_ |
Ian Rogers | ad0b3a3 | 2012-04-16 14:50:24 -0700 | [diff] [blame] | 288 | const uint32_t num_regs_; |
Ian Rogers | 776ac1f | 2012-04-13 23:36:36 -0700 | [diff] [blame] | 289 | // A stack of monitor enter locations |
| 290 | std::deque<uint32_t> monitors_; |
| 291 | // A map from register to a bit vector of indices into the monitors_ stack. As we pop the monitor |
| 292 | // stack we verify that monitor-enter/exit are correctly nested. That is, if there was a |
| 293 | // monitor-enter on v5 and then on v6, we expect the monitor-exit to be on v6 then on v5 |
| 294 | SafeMap<uint32_t, uint32_t> reg_to_lock_depths_; |
| 295 | }; |
| 296 | std::ostream& operator<<(std::ostream& os, const RegisterLine& rhs); |
| 297 | |
| 298 | } // namespace verifier |
| 299 | } // namespace art |
| 300 | |
| 301 | #endif // ART_SRC_VERIFIER_REGISTER_LINE_H_ |