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_REG_TYPE_H_ 18 #define ART_RUNTIME_VERIFIER_REG_TYPE_H_ 19 20 #include <stdint.h> 21 #include <limits> 22 #include <set> 23 #include <string> 24 25 #include "base/bit_vector.h" 26 #include "base/macros.h" 27 #include "base/mutex.h" 28 #include "gc_root.h" 29 #include "handle_scope.h" 30 #include "object_callbacks.h" 31 #include "primitive.h" 32 33 namespace art { 34 namespace mirror { 35 class Class; 36 } // namespace mirror 37 38 namespace verifier { 39 40 class RegTypeCache; 41 /* 42 * RegType holds information about the "type" of data held in a register. 43 */ 44 class RegType { 45 public: IsUndefined()46 virtual bool IsUndefined() const { return false; } IsConflict()47 virtual bool IsConflict() const { return false; } IsBoolean()48 virtual bool IsBoolean() const { return false; } IsByte()49 virtual bool IsByte() const { return false; } IsChar()50 virtual bool IsChar() const { return false; } IsShort()51 virtual bool IsShort() const { return false; } IsInteger()52 virtual bool IsInteger() const { return false; } IsLongLo()53 virtual bool IsLongLo() const { return false; } IsLongHi()54 virtual bool IsLongHi() const { return false; } IsFloat()55 virtual bool IsFloat() const { return false; } IsDouble()56 virtual bool IsDouble() const { return false; } IsDoubleLo()57 virtual bool IsDoubleLo() const { return false; } IsDoubleHi()58 virtual bool IsDoubleHi() const { return false; } IsUnresolvedReference()59 virtual bool IsUnresolvedReference() const { return false; } IsUninitializedReference()60 virtual bool IsUninitializedReference() const { return false; } IsUninitializedThisReference()61 virtual bool IsUninitializedThisReference() const { return false; } IsUnresolvedAndUninitializedReference()62 virtual bool IsUnresolvedAndUninitializedReference() const { return false; } IsUnresolvedAndUninitializedThisReference()63 virtual bool IsUnresolvedAndUninitializedThisReference() const { 64 return false; 65 } IsUnresolvedMergedReference()66 virtual bool IsUnresolvedMergedReference() const { return false; } IsUnresolvedSuperClass()67 virtual bool IsUnresolvedSuperClass() const { return false; } IsReference()68 virtual bool IsReference() const { return false; } IsPreciseReference()69 virtual bool IsPreciseReference() const { return false; } IsPreciseConstant()70 virtual bool IsPreciseConstant() const { return false; } IsPreciseConstantLo()71 virtual bool IsPreciseConstantLo() const { return false; } IsPreciseConstantHi()72 virtual bool IsPreciseConstantHi() const { return false; } IsImpreciseConstantLo()73 virtual bool IsImpreciseConstantLo() const { return false; } IsImpreciseConstantHi()74 virtual bool IsImpreciseConstantHi() const { return false; } IsImpreciseConstant()75 virtual bool IsImpreciseConstant() const { return false; } IsConstantTypes()76 virtual bool IsConstantTypes() const { return false; } IsConstant()77 bool IsConstant() const { 78 return IsImpreciseConstant() || IsPreciseConstant(); 79 } IsConstantLo()80 bool IsConstantLo() const { 81 return IsImpreciseConstantLo() || IsPreciseConstantLo(); 82 } IsPrecise()83 bool IsPrecise() const { 84 return IsPreciseConstantLo() || IsPreciseConstant() || 85 IsPreciseConstantHi(); 86 } IsLongConstant()87 bool IsLongConstant() const { return IsConstantLo(); } IsConstantHi()88 bool IsConstantHi() const { 89 return (IsPreciseConstantHi() || IsImpreciseConstantHi()); 90 } IsLongConstantHigh()91 bool IsLongConstantHigh() const { return IsConstantHi(); } IsUninitializedTypes()92 virtual bool IsUninitializedTypes() const { return false; } IsUnresolvedTypes()93 virtual bool IsUnresolvedTypes() const { return false; } 94 IsLowHalf()95 bool IsLowHalf() const { 96 return (IsLongLo() || IsDoubleLo() || IsPreciseConstantLo() || IsImpreciseConstantLo()); 97 } IsHighHalf()98 bool IsHighHalf() const { 99 return (IsLongHi() || IsDoubleHi() || IsPreciseConstantHi() || IsImpreciseConstantHi()); 100 } IsLongOrDoubleTypes()101 bool IsLongOrDoubleTypes() const { return IsLowHalf(); } 102 // Check this is the low half, and that type_h is its matching high-half. CheckWidePair(const RegType & type_h)103 inline bool CheckWidePair(const RegType& type_h) const { 104 if (IsLowHalf()) { 105 return ((IsImpreciseConstantLo() && type_h.IsPreciseConstantHi()) || 106 (IsImpreciseConstantLo() && type_h.IsImpreciseConstantHi()) || 107 (IsPreciseConstantLo() && type_h.IsPreciseConstantHi()) || 108 (IsPreciseConstantLo() && type_h.IsImpreciseConstantHi()) || 109 (IsDoubleLo() && type_h.IsDoubleHi()) || 110 (IsLongLo() && type_h.IsLongHi())); 111 } 112 return false; 113 } 114 // The high half that corresponds to this low half 115 const RegType& HighHalf(RegTypeCache* cache) const 116 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 117 118 bool IsConstantBoolean() const; IsConstantChar()119 virtual bool IsConstantChar() const { return false; } IsConstantByte()120 virtual bool IsConstantByte() const { return false; } IsConstantShort()121 virtual bool IsConstantShort() const { return false; } IsOne()122 virtual bool IsOne() const { return false; } IsZero()123 virtual bool IsZero() const { return false; } IsReferenceTypes()124 bool IsReferenceTypes() const { 125 return IsNonZeroReferenceTypes() || IsZero(); 126 } IsNonZeroReferenceTypes()127 virtual bool IsNonZeroReferenceTypes() const { return false; } IsCategory1Types()128 bool IsCategory1Types() const { 129 return IsChar() || IsInteger() || IsFloat() || IsConstant() || IsByte() || 130 IsShort() || IsBoolean(); 131 } IsCategory2Types()132 bool IsCategory2Types() const { 133 return IsLowHalf(); // Don't expect explicit testing of high halves 134 } IsBooleanTypes()135 bool IsBooleanTypes() const { return IsBoolean() || IsConstantBoolean(); } IsByteTypes()136 bool IsByteTypes() const { 137 return IsConstantByte() || IsByte() || IsBoolean(); 138 } IsShortTypes()139 bool IsShortTypes() const { 140 return IsShort() || IsByte() || IsBoolean() || IsConstantShort(); 141 } IsCharTypes()142 bool IsCharTypes() const { 143 return IsChar() || IsBooleanTypes() || IsConstantChar(); 144 } IsIntegralTypes()145 bool IsIntegralTypes() const { 146 return IsInteger() || IsConstant() || IsByte() || IsShort() || IsChar() || 147 IsBoolean(); 148 } 149 // Give the constant value encoded, but this shouldn't be called in the 150 // general case. IsArrayIndexTypes()151 bool IsArrayIndexTypes() const { return IsIntegralTypes(); } 152 // Float type may be derived from any constant type IsFloatTypes()153 bool IsFloatTypes() const { return IsFloat() || IsConstant(); } IsLongTypes()154 bool IsLongTypes() const { return IsLongLo() || IsLongConstant(); } IsLongHighTypes()155 bool IsLongHighTypes() const { 156 return (IsLongHi() || IsPreciseConstantHi() || IsImpreciseConstantHi()); 157 } IsDoubleTypes()158 bool IsDoubleTypes() const { return IsDoubleLo() || IsLongConstant(); } IsDoubleHighTypes()159 bool IsDoubleHighTypes() const { 160 return (IsDoubleHi() || IsPreciseConstantHi() || IsImpreciseConstantHi()); 161 } IsLong()162 virtual bool IsLong() const { return false; } HasClass()163 bool HasClass() const { 164 bool result = !klass_.IsNull(); 165 DCHECK_EQ(result, HasClassVirtual()); 166 return result; 167 } HasClassVirtual()168 virtual bool HasClassVirtual() const { return false; } 169 bool IsJavaLangObject() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 170 bool IsArrayTypes() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 171 bool IsObjectArrayTypes() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 172 Primitive::Type GetPrimitiveType() const; 173 bool IsJavaLangObjectArray() const 174 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 175 bool IsInstantiableTypes() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); GetDescriptor()176 const std::string& GetDescriptor() const { 177 DCHECK(HasClass() || 178 (IsUnresolvedTypes() && !IsUnresolvedMergedReference() && 179 !IsUnresolvedSuperClass())); 180 return descriptor_; 181 } GetClass()182 mirror::Class* GetClass() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 183 DCHECK(!IsUnresolvedReference()); 184 DCHECK(!klass_.IsNull()) << Dump(); 185 DCHECK(HasClass()); 186 return klass_.Read(); 187 } GetId()188 uint16_t GetId() const { return cache_id_; } 189 const RegType& GetSuperClass(RegTypeCache* cache) const 190 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 191 192 virtual std::string Dump() const 193 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) = 0; 194 195 // Can this type access other? 196 bool CanAccess(const RegType& other) const 197 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 198 199 // Can this type access a member with the given properties? 200 bool CanAccessMember(mirror::Class* klass, uint32_t access_flags) const 201 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 202 203 // Can this type be assigned by src? 204 // Note: Object and interface types may always be assigned to one another, see 205 // comment on 206 // ClassJoin. 207 bool IsAssignableFrom(const RegType& src) const 208 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 209 210 // Can this array type potentially be assigned by src. 211 // This function is necessary as array types are valid even if their components types are not, 212 // e.g., when they component type could not be resolved. The function will return true iff the 213 // types are assignable. It will return false otherwise. In case of return=false, soft_error 214 // will be set to true iff the assignment test failure should be treated as a soft-error, i.e., 215 // when both array types have the same 'depth' and the 'final' component types may be assignable 216 // (both are reference types). 217 bool CanAssignArray(const RegType& src, RegTypeCache& reg_types, 218 Handle<mirror::ClassLoader> class_loader, bool* soft_error) const 219 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 220 221 // Can this type be assigned by src? Variant of IsAssignableFrom that doesn't 222 // allow assignment to 223 // an interface from an Object. 224 bool IsStrictlyAssignableFrom(const RegType& src) const 225 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 226 227 // Are these RegTypes the same? Equals(const RegType & other)228 bool Equals(const RegType& other) const { return GetId() == other.GetId(); } 229 230 // Compute the merge of this register from one edge (path) with incoming_type 231 // from another. 232 const RegType& Merge(const RegType& incoming_type, RegTypeCache* reg_types) const 233 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 234 // Same as above, but also handles the case where incoming_type == this. SafeMerge(const RegType & incoming_type,RegTypeCache * reg_types)235 const RegType& SafeMerge(const RegType& incoming_type, RegTypeCache* reg_types) const 236 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 237 if (Equals(incoming_type)) { 238 return *this; 239 } 240 return Merge(incoming_type, reg_types); 241 } 242 243 /* 244 * A basic Join operation on classes. For a pair of types S and T the Join, 245 *written S v T = J, is 246 * S <: J, T <: J and for-all U such that S <: U, T <: U then J <: U. That is 247 *J is the parent of 248 * S and T such that there isn't a parent of both S and T that isn't also the 249 *parent of J (ie J 250 * is the deepest (lowest upper bound) parent of S and T). 251 * 252 * This operation applies for regular classes and arrays, however, for 253 *interface types there 254 * needn't be a partial ordering on the types. We could solve the problem of a 255 *lack of a partial 256 * order by introducing sets of types, however, the only operation permissible 257 *on an interface is 258 * invoke-interface. In the tradition of Java verifiers [1] we defer the 259 *verification of interface 260 * types until an invoke-interface call on the interface typed reference at 261 *runtime and allow 262 * the perversion of Object being assignable to an interface type (note, 263 *however, that we don't 264 * allow assignment of Object or Interface to any concrete class and are 265 *therefore type safe). 266 * 267 * [1] Java bytecode verification: algorithms and formalizations, Xavier Leroy 268 */ 269 static mirror::Class* ClassJoin(mirror::Class* s, mirror::Class* t) 270 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 271 ~RegType()272 virtual ~RegType() {} 273 274 void VisitRoots(RootVisitor* visitor, const RootInfo& root_info) const 275 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 276 277 protected: RegType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)278 RegType(mirror::Class* klass, const std::string& descriptor, 279 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 280 : descriptor_(descriptor), klass_(klass), cache_id_(cache_id) { 281 if (kIsDebugBuild) { 282 CheckInvariants(); 283 } 284 } 285 286 void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 287 288 const std::string descriptor_; 289 mutable GcRoot<mirror::Class> 290 klass_; // Non-const only due to moving classes. 291 const uint16_t cache_id_; 292 293 friend class RegTypeCache; 294 295 private: 296 static bool AssignableFrom(const RegType& lhs, const RegType& rhs, bool strict) 297 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 298 299 DISALLOW_COPY_AND_ASSIGN(RegType); 300 }; 301 302 // Bottom type. 303 class ConflictType FINAL : public RegType { 304 public: IsConflict()305 bool IsConflict() const OVERRIDE { return true; } 306 307 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 308 309 // Get the singleton Conflict instance. 310 static const ConflictType* GetInstance() PURE; 311 312 // Create the singleton instance. 313 static const ConflictType* CreateInstance(mirror::Class* klass, 314 const std::string& descriptor, 315 uint16_t cache_id) 316 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 317 318 // Destroy the singleton instance. 319 static void Destroy(); 320 321 private: ConflictType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)322 ConflictType(mirror::Class* klass, const std::string& descriptor, 323 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 324 : RegType(klass, descriptor, cache_id) {} 325 326 static const ConflictType* instance_; 327 }; 328 329 // A variant of the bottom type used to specify an undefined value in the 330 // incoming registers. 331 // Merging with UndefinedType yields ConflictType which is the true bottom. 332 class UndefinedType FINAL : public RegType { 333 public: IsUndefined()334 bool IsUndefined() const OVERRIDE { return true; } 335 336 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 337 338 // Get the singleton Undefined instance. 339 static const UndefinedType* GetInstance() PURE; 340 341 // Create the singleton instance. 342 static const UndefinedType* CreateInstance(mirror::Class* klass, 343 const std::string& descriptor, 344 uint16_t cache_id) 345 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 346 347 // Destroy the singleton instance. 348 static void Destroy(); 349 350 private: UndefinedType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)351 UndefinedType(mirror::Class* klass, const std::string& descriptor, 352 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 353 : RegType(klass, descriptor, cache_id) {} 354 355 static const UndefinedType* instance_; 356 }; 357 358 class PrimitiveType : public RegType { 359 public: 360 PrimitiveType(mirror::Class* klass, const std::string& descriptor, 361 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 362 HasClassVirtual()363 bool HasClassVirtual() const OVERRIDE { return true; } 364 }; 365 366 class Cat1Type : public PrimitiveType { 367 public: 368 Cat1Type(mirror::Class* klass, const std::string& descriptor, 369 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 370 }; 371 372 class IntegerType : public Cat1Type { 373 public: IsInteger()374 bool IsInteger() const OVERRIDE { return true; } 375 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 376 static const IntegerType* CreateInstance(mirror::Class* klass, 377 const std::string& descriptor, 378 uint16_t cache_id) 379 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 380 static const IntegerType* GetInstance() PURE; 381 static void Destroy(); 382 383 private: IntegerType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)384 IntegerType(mirror::Class* klass, const std::string& descriptor, 385 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 386 : Cat1Type(klass, descriptor, cache_id) {} 387 static const IntegerType* instance_; 388 }; 389 390 class BooleanType FINAL : public Cat1Type { 391 public: IsBoolean()392 bool IsBoolean() const OVERRIDE { return true; } 393 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 394 static const BooleanType* CreateInstance(mirror::Class* klass, 395 const std::string& descriptor, 396 uint16_t cache_id) 397 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 398 static const BooleanType* GetInstance() PURE; 399 static void Destroy(); 400 401 private: BooleanType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)402 BooleanType(mirror::Class* klass, const std::string& descriptor, 403 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 404 : Cat1Type(klass, descriptor, cache_id) {} 405 406 static const BooleanType* instance_; 407 }; 408 409 class ByteType FINAL : public Cat1Type { 410 public: IsByte()411 bool IsByte() const OVERRIDE { return true; } 412 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 413 static const ByteType* CreateInstance(mirror::Class* klass, 414 const std::string& descriptor, 415 uint16_t cache_id) 416 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 417 static const ByteType* GetInstance() PURE; 418 static void Destroy(); 419 420 private: ByteType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)421 ByteType(mirror::Class* klass, const std::string& descriptor, 422 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 423 : Cat1Type(klass, descriptor, cache_id) {} 424 static const ByteType* instance_; 425 }; 426 427 class ShortType FINAL : public Cat1Type { 428 public: IsShort()429 bool IsShort() const OVERRIDE { return true; } 430 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 431 static const ShortType* CreateInstance(mirror::Class* klass, 432 const std::string& descriptor, 433 uint16_t cache_id) 434 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 435 static const ShortType* GetInstance() PURE; 436 static void Destroy(); 437 438 private: ShortType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)439 ShortType(mirror::Class* klass, const std::string& descriptor, 440 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 441 : Cat1Type(klass, descriptor, cache_id) {} 442 static const ShortType* instance_; 443 }; 444 445 class CharType FINAL : public Cat1Type { 446 public: IsChar()447 bool IsChar() const OVERRIDE { return true; } 448 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 449 static const CharType* CreateInstance(mirror::Class* klass, 450 const std::string& descriptor, 451 uint16_t cache_id) 452 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 453 static const CharType* GetInstance() PURE; 454 static void Destroy(); 455 456 private: CharType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)457 CharType(mirror::Class* klass, const std::string& descriptor, 458 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 459 : Cat1Type(klass, descriptor, cache_id) {} 460 static const CharType* instance_; 461 }; 462 463 class FloatType FINAL : public Cat1Type { 464 public: IsFloat()465 bool IsFloat() const OVERRIDE { return true; } 466 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 467 static const FloatType* CreateInstance(mirror::Class* klass, 468 const std::string& descriptor, 469 uint16_t cache_id) 470 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 471 static const FloatType* GetInstance() PURE; 472 static void Destroy(); 473 474 private: FloatType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)475 FloatType(mirror::Class* klass, const std::string& descriptor, 476 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 477 : Cat1Type(klass, descriptor, cache_id) {} 478 static const FloatType* instance_; 479 }; 480 481 class Cat2Type : public PrimitiveType { 482 public: 483 Cat2Type(mirror::Class* klass, const std::string& descriptor, 484 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 485 }; 486 487 class LongLoType FINAL : public Cat2Type { 488 public: 489 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); IsLongLo()490 bool IsLongLo() const OVERRIDE { return true; } IsLong()491 bool IsLong() const OVERRIDE { return true; } 492 static const LongLoType* CreateInstance(mirror::Class* klass, 493 const std::string& descriptor, 494 uint16_t cache_id) 495 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 496 static const LongLoType* GetInstance() PURE; 497 static void Destroy(); 498 499 private: LongLoType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)500 LongLoType(mirror::Class* klass, const std::string& descriptor, 501 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 502 : Cat2Type(klass, descriptor, cache_id) {} 503 static const LongLoType* instance_; 504 }; 505 506 class LongHiType FINAL : public Cat2Type { 507 public: 508 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); IsLongHi()509 bool IsLongHi() const OVERRIDE { return true; } 510 static const LongHiType* CreateInstance(mirror::Class* klass, 511 const std::string& descriptor, 512 uint16_t cache_id) 513 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 514 static const LongHiType* GetInstance() PURE; 515 static void Destroy(); 516 517 private: LongHiType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)518 LongHiType(mirror::Class* klass, const std::string& descriptor, 519 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 520 : Cat2Type(klass, descriptor, cache_id) {} 521 static const LongHiType* instance_; 522 }; 523 524 class DoubleLoType FINAL : public Cat2Type { 525 public: 526 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); IsDoubleLo()527 bool IsDoubleLo() const OVERRIDE { return true; } IsDouble()528 bool IsDouble() const OVERRIDE { return true; } 529 static const DoubleLoType* CreateInstance(mirror::Class* klass, 530 const std::string& descriptor, 531 uint16_t cache_id) 532 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 533 static const DoubleLoType* GetInstance() PURE; 534 static void Destroy(); 535 536 private: DoubleLoType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)537 DoubleLoType(mirror::Class* klass, const std::string& descriptor, 538 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 539 : Cat2Type(klass, descriptor, cache_id) {} 540 static const DoubleLoType* instance_; 541 }; 542 543 class DoubleHiType FINAL : public Cat2Type { 544 public: 545 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); IsDoubleHi()546 virtual bool IsDoubleHi() const OVERRIDE { return true; } 547 static const DoubleHiType* CreateInstance(mirror::Class* klass, 548 const std::string& descriptor, 549 uint16_t cache_id) 550 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 551 static const DoubleHiType* GetInstance() PURE; 552 static void Destroy(); 553 554 private: DoubleHiType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)555 DoubleHiType(mirror::Class* klass, const std::string& descriptor, 556 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 557 : Cat2Type(klass, descriptor, cache_id) {} 558 static const DoubleHiType* instance_; 559 }; 560 561 class ConstantType : public RegType { 562 public: ConstantType(uint32_t constant,uint16_t cache_id)563 ConstantType(uint32_t constant, uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 564 : RegType(nullptr, "", cache_id), constant_(constant) { 565 } 566 567 568 // If this is a 32-bit constant, what is the value? This value may be 569 // imprecise in which case 570 // the value represents part of the integer range of values that may be held 571 // in the register. ConstantValue()572 int32_t ConstantValue() const { 573 DCHECK(IsConstantTypes()); 574 return constant_; 575 } 576 ConstantValueLo()577 int32_t ConstantValueLo() const { 578 DCHECK(IsConstantLo()); 579 return constant_; 580 } 581 ConstantValueHi()582 int32_t ConstantValueHi() const { 583 if (IsConstantHi() || IsPreciseConstantHi() || IsImpreciseConstantHi()) { 584 return constant_; 585 } else { 586 DCHECK(false); 587 return 0; 588 } 589 } 590 IsZero()591 bool IsZero() const OVERRIDE { 592 return IsPreciseConstant() && ConstantValue() == 0; 593 } IsOne()594 bool IsOne() const OVERRIDE { 595 return IsPreciseConstant() && ConstantValue() == 1; 596 } 597 IsConstantChar()598 bool IsConstantChar() const OVERRIDE { 599 return IsConstant() && ConstantValue() >= 0 && 600 ConstantValue() <= std::numeric_limits<uint16_t>::max(); 601 } IsConstantByte()602 bool IsConstantByte() const OVERRIDE { 603 return IsConstant() && 604 ConstantValue() >= std::numeric_limits<int8_t>::min() && 605 ConstantValue() <= std::numeric_limits<int8_t>::max(); 606 } IsConstantShort()607 bool IsConstantShort() const OVERRIDE { 608 return IsConstant() && 609 ConstantValue() >= std::numeric_limits<int16_t>::min() && 610 ConstantValue() <= std::numeric_limits<int16_t>::max(); 611 } IsConstantTypes()612 virtual bool IsConstantTypes() const OVERRIDE { return true; } 613 614 private: 615 const uint32_t constant_; 616 }; 617 618 class PreciseConstType FINAL : public ConstantType { 619 public: PreciseConstType(uint32_t constant,uint16_t cache_id)620 PreciseConstType(uint32_t constant, uint16_t cache_id) 621 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 622 : ConstantType(constant, cache_id) {} 623 IsPreciseConstant()624 bool IsPreciseConstant() const OVERRIDE { return true; } 625 626 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 627 }; 628 629 class PreciseConstLoType FINAL : public ConstantType { 630 public: PreciseConstLoType(uint32_t constant,uint16_t cache_id)631 PreciseConstLoType(uint32_t constant, uint16_t cache_id) 632 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 633 : ConstantType(constant, cache_id) {} IsPreciseConstantLo()634 bool IsPreciseConstantLo() const OVERRIDE { return true; } 635 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 636 }; 637 638 class PreciseConstHiType FINAL : public ConstantType { 639 public: PreciseConstHiType(uint32_t constant,uint16_t cache_id)640 PreciseConstHiType(uint32_t constant, uint16_t cache_id) 641 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 642 : ConstantType(constant, cache_id) {} IsPreciseConstantHi()643 bool IsPreciseConstantHi() const OVERRIDE { return true; } 644 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 645 }; 646 647 class ImpreciseConstType FINAL : public ConstantType { 648 public: ImpreciseConstType(uint32_t constat,uint16_t cache_id)649 ImpreciseConstType(uint32_t constat, uint16_t cache_id) 650 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 651 : ConstantType(constat, cache_id) { 652 } IsImpreciseConstant()653 bool IsImpreciseConstant() const OVERRIDE { return true; } 654 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 655 }; 656 657 class ImpreciseConstLoType FINAL : public ConstantType { 658 public: ImpreciseConstLoType(uint32_t constant,uint16_t cache_id)659 ImpreciseConstLoType(uint32_t constant, uint16_t cache_id) 660 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 661 : ConstantType(constant, cache_id) {} IsImpreciseConstantLo()662 bool IsImpreciseConstantLo() const OVERRIDE { return true; } 663 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 664 }; 665 666 class ImpreciseConstHiType FINAL : public ConstantType { 667 public: ImpreciseConstHiType(uint32_t constant,uint16_t cache_id)668 ImpreciseConstHiType(uint32_t constant, uint16_t cache_id) 669 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 670 : ConstantType(constant, cache_id) {} IsImpreciseConstantHi()671 bool IsImpreciseConstantHi() const OVERRIDE { return true; } 672 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 673 }; 674 675 // Common parent of all uninitialized types. Uninitialized types are created by 676 // "new" dex 677 // instructions and must be passed to a constructor. 678 class UninitializedType : public RegType { 679 public: UninitializedType(mirror::Class * klass,const std::string & descriptor,uint32_t allocation_pc,uint16_t cache_id)680 UninitializedType(mirror::Class* klass, const std::string& descriptor, 681 uint32_t allocation_pc, uint16_t cache_id) 682 : RegType(klass, descriptor, cache_id), allocation_pc_(allocation_pc) {} 683 684 bool IsUninitializedTypes() const OVERRIDE; 685 bool IsNonZeroReferenceTypes() const OVERRIDE; 686 GetAllocationPc()687 uint32_t GetAllocationPc() const { 688 DCHECK(IsUninitializedTypes()); 689 return allocation_pc_; 690 } 691 692 private: 693 const uint32_t allocation_pc_; 694 }; 695 696 // Similar to ReferenceType but not yet having been passed to a constructor. 697 class UninitializedReferenceType FINAL : public UninitializedType { 698 public: UninitializedReferenceType(mirror::Class * klass,const std::string & descriptor,uint32_t allocation_pc,uint16_t cache_id)699 UninitializedReferenceType(mirror::Class* klass, 700 const std::string& descriptor, 701 uint32_t allocation_pc, uint16_t cache_id) 702 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 703 : UninitializedType(klass, descriptor, allocation_pc, cache_id) {} 704 IsUninitializedReference()705 bool IsUninitializedReference() const OVERRIDE { return true; } 706 HasClassVirtual()707 bool HasClassVirtual() const OVERRIDE { return true; } 708 709 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 710 }; 711 712 // Similar to UnresolvedReferenceType but not yet having been passed to a 713 // constructor. 714 class UnresolvedUninitializedRefType FINAL : public UninitializedType { 715 public: UnresolvedUninitializedRefType(const std::string & descriptor,uint32_t allocation_pc,uint16_t cache_id)716 UnresolvedUninitializedRefType(const std::string& descriptor, 717 uint32_t allocation_pc, uint16_t cache_id) 718 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 719 : UninitializedType(nullptr, descriptor, allocation_pc, cache_id) { 720 if (kIsDebugBuild) { 721 CheckInvariants(); 722 } 723 } 724 IsUnresolvedAndUninitializedReference()725 bool IsUnresolvedAndUninitializedReference() const OVERRIDE { return true; } 726 IsUnresolvedTypes()727 bool IsUnresolvedTypes() const OVERRIDE { return true; } 728 729 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 730 731 private: 732 void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 733 }; 734 735 // Similar to UninitializedReferenceType but special case for the this argument 736 // of a constructor. 737 class UninitializedThisReferenceType FINAL : public UninitializedType { 738 public: UninitializedThisReferenceType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)739 UninitializedThisReferenceType(mirror::Class* klass, 740 const std::string& descriptor, 741 uint16_t cache_id) 742 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 743 : UninitializedType(klass, descriptor, 0, cache_id) { 744 if (kIsDebugBuild) { 745 CheckInvariants(); 746 } 747 } 748 IsUninitializedThisReference()749 virtual bool IsUninitializedThisReference() const OVERRIDE { return true; } 750 HasClassVirtual()751 bool HasClassVirtual() const OVERRIDE { return true; } 752 753 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 754 755 private: 756 void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 757 }; 758 759 class UnresolvedUninitializedThisRefType FINAL : public UninitializedType { 760 public: UnresolvedUninitializedThisRefType(const std::string & descriptor,uint16_t cache_id)761 UnresolvedUninitializedThisRefType(const std::string& descriptor, 762 uint16_t cache_id) 763 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 764 : UninitializedType(nullptr, descriptor, 0, cache_id) { 765 if (kIsDebugBuild) { 766 CheckInvariants(); 767 } 768 } 769 IsUnresolvedAndUninitializedThisReference()770 bool IsUnresolvedAndUninitializedThisReference() const OVERRIDE { return true; } 771 IsUnresolvedTypes()772 bool IsUnresolvedTypes() const OVERRIDE { return true; } 773 774 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 775 776 private: 777 void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 778 }; 779 780 // A type of register holding a reference to an Object of type GetClass or a 781 // sub-class. 782 class ReferenceType FINAL : public RegType { 783 public: ReferenceType(mirror::Class * klass,const std::string & descriptor,uint16_t cache_id)784 ReferenceType(mirror::Class* klass, const std::string& descriptor, 785 uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 786 : RegType(klass, descriptor, cache_id) {} 787 IsReference()788 bool IsReference() const OVERRIDE { return true; } 789 IsNonZeroReferenceTypes()790 bool IsNonZeroReferenceTypes() const OVERRIDE { return true; } 791 HasClassVirtual()792 bool HasClassVirtual() const OVERRIDE { return true; } 793 794 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 795 }; 796 797 // A type of register holding a reference to an Object of type GetClass and only 798 // an object of that 799 // type. 800 class PreciseReferenceType FINAL : public RegType { 801 public: 802 PreciseReferenceType(mirror::Class* klass, const std::string& descriptor, 803 uint16_t cache_id) 804 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 805 IsPreciseReference()806 bool IsPreciseReference() const OVERRIDE { return true; } 807 IsNonZeroReferenceTypes()808 bool IsNonZeroReferenceTypes() const OVERRIDE { return true; } 809 HasClassVirtual()810 bool HasClassVirtual() const OVERRIDE { return true; } 811 812 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 813 }; 814 815 // Common parent of unresolved types. 816 class UnresolvedType : public RegType { 817 public: UnresolvedType(const std::string & descriptor,uint16_t cache_id)818 UnresolvedType(const std::string& descriptor, uint16_t cache_id) 819 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 820 : RegType(nullptr, descriptor, cache_id) {} 821 822 bool IsNonZeroReferenceTypes() const OVERRIDE; 823 }; 824 825 // Similar to ReferenceType except the Class couldn't be loaded. Assignability 826 // and other tests made 827 // of this type must be conservative. 828 class UnresolvedReferenceType FINAL : public UnresolvedType { 829 public: UnresolvedReferenceType(const std::string & descriptor,uint16_t cache_id)830 UnresolvedReferenceType(const std::string& descriptor, uint16_t cache_id) 831 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 832 : UnresolvedType(descriptor, cache_id) { 833 if (kIsDebugBuild) { 834 CheckInvariants(); 835 } 836 } 837 IsUnresolvedReference()838 bool IsUnresolvedReference() const OVERRIDE { return true; } 839 IsUnresolvedTypes()840 bool IsUnresolvedTypes() const OVERRIDE { return true; } 841 842 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 843 844 private: 845 void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 846 }; 847 848 // Type representing the super-class of an unresolved type. 849 class UnresolvedSuperClass FINAL : public UnresolvedType { 850 public: UnresolvedSuperClass(uint16_t child_id,RegTypeCache * reg_type_cache,uint16_t cache_id)851 UnresolvedSuperClass(uint16_t child_id, RegTypeCache* reg_type_cache, 852 uint16_t cache_id) 853 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 854 : UnresolvedType("", cache_id), 855 unresolved_child_id_(child_id), 856 reg_type_cache_(reg_type_cache) { 857 if (kIsDebugBuild) { 858 CheckInvariants(); 859 } 860 } 861 IsUnresolvedSuperClass()862 bool IsUnresolvedSuperClass() const OVERRIDE { return true; } 863 IsUnresolvedTypes()864 bool IsUnresolvedTypes() const OVERRIDE { return true; } 865 GetUnresolvedSuperClassChildId()866 uint16_t GetUnresolvedSuperClassChildId() const { 867 DCHECK(IsUnresolvedSuperClass()); 868 return static_cast<uint16_t>(unresolved_child_id_ & 0xFFFF); 869 } 870 871 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 872 873 private: 874 void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 875 876 const uint16_t unresolved_child_id_; 877 const RegTypeCache* const reg_type_cache_; 878 }; 879 880 // A merge of unresolved (and resolved) types. If the types were resolved this may be 881 // Conflict or another known ReferenceType. 882 class UnresolvedMergedType FINAL : public UnresolvedType { 883 public: 884 // Note: the constructor will copy the unresolved BitVector, not use it directly. 885 UnresolvedMergedType(const RegType& resolved, const BitVector& unresolved, 886 const RegTypeCache* reg_type_cache, uint16_t cache_id) 887 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 888 889 // The resolved part. See description below. GetResolvedPart()890 const RegType& GetResolvedPart() const { 891 return resolved_part_; 892 } 893 // The unresolved part. GetUnresolvedTypes()894 const BitVector& GetUnresolvedTypes() const { 895 return unresolved_types_; 896 } 897 IsUnresolvedMergedReference()898 bool IsUnresolvedMergedReference() const OVERRIDE { return true; } 899 IsUnresolvedTypes()900 bool IsUnresolvedTypes() const OVERRIDE { return true; } 901 902 std::string Dump() const OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 903 904 private: 905 void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 906 907 const RegTypeCache* const reg_type_cache_; 908 909 // The original implementation of merged types was a binary tree. Collection of the flattened 910 // types ("leaves") can be expensive, so we store the expanded list now, as two components: 911 // 1) A resolved component. We use Zero when there is no resolved component, as that will be 912 // an identity merge. 913 // 2) A bitvector of the unresolved reference types. A bitvector was chosen with the assumption 914 // that there should not be too many types in flight in practice. (We also bias the index 915 // against the index of Zero, which is one of the later default entries in any cache.) 916 const RegType& resolved_part_; 917 const BitVector unresolved_types_; 918 }; 919 920 std::ostream& operator<<(std::ostream& os, const RegType& rhs) 921 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 922 923 } // namespace verifier 924 } // namespace art 925 926 #endif // ART_RUNTIME_VERIFIER_REG_TYPE_H_ 927