lib/StaticAnalyzer/EntoSA/BasicStore.cpp

   1 //== BasicStore.cpp - Basic map from Locations to Values --------*- C++ -*--==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defined the BasicStore and BasicStoreManager classes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/AST/DeclCXX.h"
  15 #include "clang/AST/ExprObjC.h"
  16 #include "clang/Analysis/Analyses/LiveVariables.h"
  17 #include "clang/Analysis/AnalysisContext.h"
  18 #include "clang/StaticAnalyzer/PathSensitive/GRState.h"
  19 #include "llvm/ADT/ImmutableMap.h"
  20
  21 using namespace clang;
  22 using namespace ento;
  23
  24 typedef llvm::ImmutableMap<const MemRegion*,SVal> BindingsTy;
  25
  26 namespace {
  27
  28 class BasicStoreSubRegionMap : public SubRegionMap {
  29 public:
  30   BasicStoreSubRegionMap() {}
  31
  32   bool iterSubRegions(const MemRegion* R, Visitor& V) const {
  33     return true; // Do nothing.  No subregions.
  34   }
  35 };
  36
  37 class BasicStoreManager : public StoreManager {
  38   BindingsTy::Factory VBFactory;
  39 public:
  40   BasicStoreManager(GRStateManager& mgr)
  41     : StoreManager(mgr), VBFactory(mgr.getAllocator()) {}
  42
  43   ~BasicStoreManager() {}
  44
  45   SubRegionMap *getSubRegionMap(Store store) {
  46     return new BasicStoreSubRegionMap();
  47   }
  48
  49   SVal Retrieve(Store store, Loc loc, QualType T = QualType());
  50
  51   Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E,
  52                          unsigned Count, InvalidatedSymbols *IS);
  53
  54   Store InvalidateRegions(Store store, const MemRegion * const *Begin,
  55                           const MemRegion * const *End, const Expr *E,
  56                           unsigned Count, InvalidatedSymbols *IS,
  57                           bool invalidateGlobals, InvalidatedRegions *Regions);
  58
  59   Store scanForIvars(Stmt *B, const Decl* SelfDecl,
  60                      const MemRegion *SelfRegion, Store St);
  61
  62   Store Bind(Store St, Loc loc, SVal V);
  63   Store Remove(Store St, Loc loc);
  64   Store getInitialStore(const LocationContext *InitLoc);
  65
  66   Store BindCompoundLiteral(Store store, const CompoundLiteralExpr*,
  67                             const LocationContext*, SVal val) {
  68     return store;
  69   }
  70
  71   /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit
  72   ///  conversions between arrays and pointers.
  73   SVal ArrayToPointer(Loc Array) { return Array; }
  74
  75   /// RemoveDeadBindings - Scans a BasicStore of 'state' for dead values.
  76   ///  It updatees the GRState object in place with the values removed.
  77   Store RemoveDeadBindings(Store store, const StackFrameContext *LCtx,
  78                            SymbolReaper& SymReaper,
  79                           llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
  80
  81   void iterBindings(Store store, BindingsHandler& f);
  82
  83   Store BindDecl(Store store, const VarRegion *VR, SVal InitVal) {
  84     return BindDeclInternal(store, VR, &InitVal);
  85   }
  86
  87   Store BindDeclWithNoInit(Store store, const VarRegion *VR) {
  88     return BindDeclInternal(store, VR, 0);
  89   }
  90
  91   Store BindDeclInternal(Store store, const VarRegion *VR, SVal *InitVal);
  92
  93   static inline BindingsTy GetBindings(Store store) {
  94     return BindingsTy(static_cast<const BindingsTy::TreeTy*>(store));
  95   }
  96
  97   void print(Store store, llvm::raw_ostream& Out, const char* nl,
  98              const char *sep);
  99
 100 private:
 101   SVal LazyRetrieve(Store store, const TypedRegion *R);
 102 };
 103
 104 } // end anonymous namespace
 105
 106
 107 StoreManager* ento::CreateBasicStoreManager(GRStateManager& StMgr) {
 108   return new BasicStoreManager(StMgr);
 109 }
 110
 111 static bool isHigherOrderRawPtr(QualType T, ASTContext &C) {
 112   bool foundPointer = false;
 113   while (1) {
 114     const PointerType *PT = T->getAs<PointerType>();
 115     if (!PT) {
 116       if (!foundPointer)
 117         return false;
 118
 119       // intptr_t* or intptr_t**, etc?
 120       if (T->isIntegerType() && C.getTypeSize(T) == C.getTypeSize(C.VoidPtrTy))
 121         return true;
 122
 123       QualType X = C.getCanonicalType(T).getUnqualifiedType();
 124       return X == C.VoidTy;
 125     }
 126
 127     foundPointer = true;
 128     T = PT->getPointeeType();
 129   }
 130 }
 131
 132 SVal BasicStoreManager::LazyRetrieve(Store store, const TypedRegion *R) {
 133   const VarRegion *VR = dyn_cast<VarRegion>(R);
 134   if (!VR)
 135     return UnknownVal();
 136
 137   const VarDecl *VD = VR->getDecl();
 138   QualType T = VD->getType();
 139
 140   // Only handle simple types that we can symbolicate.
 141   if (!SymbolManager::canSymbolicate(T) || !T->isScalarType())
 142     return UnknownVal();
 143
 144   // Globals and parameters start with symbolic values.
 145   // Local variables initially are undefined.
 146
 147   // Non-static globals may have had their values reset by InvalidateRegions.
 148   const MemSpaceRegion *MS = VR->getMemorySpace();
 149   if (isa<NonStaticGlobalSpaceRegion>(MS)) {
 150     BindingsTy B = GetBindings(store);
 151     // FIXME: Copy-and-pasted from RegionStore.cpp.
 152     if (BindingsTy::data_type *Val = B.lookup(MS)) {
 153       if (SymbolRef parentSym = Val->getAsSymbol())
 154         return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
 155
 156       if (Val->isZeroConstant())
 157         return svalBuilder.makeZeroVal(T);
 158
 159       if (Val->isUnknownOrUndef())
 160         return *Val;
 161
 162       assert(0 && "Unknown default value.");
 163     }
 164   }
 165
 166   if (VR->hasGlobalsOrParametersStorage() ||
 167       isa<UnknownSpaceRegion>(VR->getMemorySpace()))
 168     return svalBuilder.getRegionValueSymbolVal(R);
 169
 170   return UndefinedVal();
 171 }
 172
 173 SVal BasicStoreManager::Retrieve(Store store, Loc loc, QualType T) {
 174   if (isa<UnknownVal>(loc))
 175     return UnknownVal();
 176
 177   assert(!isa<UndefinedVal>(loc));
 178
 179   switch (loc.getSubKind()) {
 180
 181     case loc::MemRegionKind: {
 182       const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
 183
 184       if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
 185           isa<CXXThisRegion>(R)))
 186         return UnknownVal();
 187
 188       BindingsTy B = GetBindings(store);
 189       BindingsTy::data_type *Val = B.lookup(R);
 190       const TypedRegion *TR = cast<TypedRegion>(R);
 191
 192       if (Val)
 193         return CastRetrievedVal(*Val, TR, T);
 194
 195       SVal V = LazyRetrieve(store, TR);
 196       return V.isUnknownOrUndef() ? V : CastRetrievedVal(V, TR, T);
 197     }
 198
 199     case loc::ConcreteIntKind:
 200       // Support direct accesses to memory.  It's up to individual checkers
 201       // to flag an error.
 202       return UnknownVal();
 203
 204     default:
 205       assert (false && "Invalid Loc.");
 206       break;
 207   }
 208
 209   return UnknownVal();
 210 }
 211
 212 Store BasicStoreManager::Bind(Store store, Loc loc, SVal V) {
 213   if (isa<loc::ConcreteInt>(loc))
 214     return store;
 215
 216   const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
 217
 218   // Special case: a default symbol assigned to the NonStaticGlobalsSpaceRegion
 219   //  that is used to derive other symbols.
 220   if (isa<NonStaticGlobalSpaceRegion>(R)) {
 221     BindingsTy B = GetBindings(store);
 222     return VBFactory.add(B, R, V).getRoot();
 223   }
 224
 225   // Special case: handle store of pointer values (Loc) to pointers via
 226   // a cast to intXX_t*, void*, etc.  This is needed to handle
 227   // OSCompareAndSwap32Barrier/OSCompareAndSwap64Barrier.
 228   if (isa<Loc>(V) || isa<nonloc::LocAsInteger>(V))
 229     if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
 230       // FIXME: Should check for index 0.
 231       QualType T = ER->getLocationType();
 232
 233       if (isHigherOrderRawPtr(T, Ctx))
 234         R = ER->getSuperRegion();
 235     }
 236
 237   if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) || isa<CXXThisRegion>(R)))
 238     return store;
 239
 240   const TypedRegion *TyR = cast<TypedRegion>(R);
 241
 242   // Do not bind to arrays.  We need to explicitly check for this so that
 243   // we do not encounter any weirdness of trying to load/store from arrays.
 244   if (TyR->isBoundable() && TyR->getValueType()->isArrayType())
 245     return store;
 246
 247   if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&V)) {
 248     // Only convert 'V' to a location iff the underlying region type
 249     // is a location as well.
 250     // FIXME: We are allowing a store of an arbitrary location to
 251     // a pointer.  We may wish to flag a type error here if the types
 252     // are incompatible.  This may also cause lots of breakage
 253     // elsewhere. Food for thought.
 254     if (TyR->isBoundable() && Loc::IsLocType(TyR->getValueType()))
 255       V = X->getLoc();
 256   }
 257
 258   BindingsTy B = GetBindings(store);
 259   return V.isUnknown()
 260     ? VBFactory.remove(B, R).getRoot()
 261     : VBFactory.add(B, R, V).getRoot();
 262 }
 263
 264 Store BasicStoreManager::Remove(Store store, Loc loc) {
 265   switch (loc.getSubKind()) {
 266     case loc::MemRegionKind: {
 267       const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
 268
 269       if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
 270           isa<CXXThisRegion>(R)))
 271         return store;
 272
 273       return VBFactory.remove(GetBindings(store), R).getRoot();
 274     }
 275     default:
 276       assert ("Remove for given Loc type not yet implemented.");
 277       return store;
 278   }
 279 }
 280
 281 Store BasicStoreManager::RemoveDeadBindings(Store store,
 282                                             const StackFrameContext *LCtx,
 283                                             SymbolReaper& SymReaper,
 284                            llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
 285 {
 286   BindingsTy B = GetBindings(store);
 287   typedef SVal::symbol_iterator symbol_iterator;
 288
 289   // Iterate over the variable bindings.
 290   for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
 291     if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) {
 292       if (SymReaper.isLive(VR))
 293         RegionRoots.push_back(VR);
 294       else
 295         continue;
 296     }
 297     else if (isa<ObjCIvarRegion>(I.getKey()) ||
 298              isa<NonStaticGlobalSpaceRegion>(I.getKey()) ||
 299              isa<CXXThisRegion>(I.getKey()))
 300       RegionRoots.push_back(I.getKey());
 301     else
 302       continue;
 303
 304     // Mark the bindings in the data as live.
 305     SVal X = I.getData();
 306     for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
 307       SymReaper.markLive(*SI);
 308   }
 309
 310   // Scan for live variables and live symbols.
 311   llvm::SmallPtrSet<const MemRegion*, 10> Marked;
 312
 313   while (!RegionRoots.empty()) {
 314     const MemRegion* MR = RegionRoots.back();
 315     RegionRoots.pop_back();
 316
 317     while (MR) {
 318       if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) {
 319         SymReaper.markLive(SymR->getSymbol());
 320         break;
 321       }
 322       else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR) ||
 323                isa<NonStaticGlobalSpaceRegion>(MR) || isa<CXXThisRegion>(MR)) {
 324         if (Marked.count(MR))
 325           break;
 326
 327         Marked.insert(MR);
 328         SVal X = Retrieve(store, loc::MemRegionVal(MR));
 329
 330         // FIXME: We need to handle symbols nested in region definitions.
 331         for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
 332           SymReaper.markLive(*SI);
 333
 334         if (!isa<loc::MemRegionVal>(X))
 335           break;
 336
 337         const loc::MemRegionVal& LVD = cast<loc::MemRegionVal>(X);
 338         RegionRoots.push_back(LVD.getRegion());
 339         break;
 340       }
 341       else if (const SubRegion* R = dyn_cast<SubRegion>(MR))
 342         MR = R->getSuperRegion();
 343       else
 344         break;
 345     }
 346   }
 347
 348   // Remove dead variable bindings.
 349   for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
 350     const MemRegion* R = I.getKey();
 351
 352     if (!Marked.count(R)) {
 353       store = Remove(store, svalBuilder.makeLoc(R));
 354       SVal X = I.getData();
 355
 356       for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
 357         SymReaper.maybeDead(*SI);
 358     }
 359   }
 360
 361   return store;
 362 }
 363
 364 Store BasicStoreManager::scanForIvars(Stmt *B, const Decl* SelfDecl,
 365                                       const MemRegion *SelfRegion, Store St) {
 366   for (Stmt::child_iterator CI=B->child_begin(), CE=B->child_end();
 367        CI != CE; ++CI) {
 368
 369     if (!*CI)
 370       continue;
 371
 372     // Check if the statement is an ivar reference.  We only
 373     // care about self.ivar.
 374     if (ObjCIvarRefExpr *IV = dyn_cast<ObjCIvarRefExpr>(*CI)) {
 375       const Expr *Base = IV->getBase()->IgnoreParenCasts();
 376       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Base)) {
 377         if (DR->getDecl() == SelfDecl) {
 378           const ObjCIvarRegion *IVR = MRMgr.getObjCIvarRegion(IV->getDecl(),
 379                                                          SelfRegion);
 380           SVal X = svalBuilder.getRegionValueSymbolVal(IVR);
 381           St = Bind(St, svalBuilder.makeLoc(IVR), X);
 382         }
 383       }
 384     }
 385     else
 386       St = scanForIvars(*CI, SelfDecl, SelfRegion, St);
 387   }
 388
 389   return St;
 390 }
 391
 392 Store BasicStoreManager::getInitialStore(const LocationContext *InitLoc) {
 393   // The LiveVariables information already has a compilation of all VarDecls
 394   // used in the function.  Iterate through this set, and "symbolicate"
 395   // any VarDecl whose value originally comes from outside the function.
 396   typedef LiveVariables::AnalysisDataTy LVDataTy;
 397   LVDataTy& D = InitLoc->getLiveVariables()->getAnalysisData();
 398   Store St = VBFactory.getEmptyMap().getRoot();
 399
 400   for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
 401     const NamedDecl* ND = I->first;
 402
 403     // Handle implicit parameters.
 404     if (const ImplicitParamDecl* PD = dyn_cast<ImplicitParamDecl>(ND)) {
 405       const Decl& CD = *InitLoc->getDecl();
 406       if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(&CD)) {
 407         if (MD->getSelfDecl() == PD) {
 408           // FIXME: Add type constraints (when they become available) to
 409           // SelfRegion?  (i.e., it implements MD->getClassInterface()).
 410           const VarRegion *VR = MRMgr.getVarRegion(PD, InitLoc);
 411           const MemRegion *SelfRegion =
 412             svalBuilder.getRegionValueSymbolVal(VR).getAsRegion();
 413           assert(SelfRegion);
 414           St = Bind(St, svalBuilder.makeLoc(VR), loc::MemRegionVal(SelfRegion));
 415           // Scan the method for ivar references.  While this requires an
 416           // entire AST scan, the cost should not be high in practice.
 417           St = scanForIvars(MD->getBody(), PD, SelfRegion, St);
 418         }
 419       }
 420     }
 421   }
 422
 423   if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(InitLoc->getDecl())) {
 424     // For C++ methods add symbolic region for 'this' in initial stack frame.
 425     QualType ThisT = MD->getThisType(StateMgr.getContext());
 426     MemRegionManager &RegMgr = svalBuilder.getRegionManager();
 427     const CXXThisRegion *ThisR = RegMgr.getCXXThisRegion(ThisT, InitLoc);
 428     SVal ThisV = svalBuilder.getRegionValueSymbolVal(ThisR);
 429     St = Bind(St, svalBuilder.makeLoc(ThisR), ThisV);
 430   }
 431
 432   return St;
 433 }
 434
 435 Store BasicStoreManager::BindDeclInternal(Store store, const VarRegion* VR,
 436                                           SVal* InitVal) {
 437
 438   BasicValueFactory& BasicVals = StateMgr.getBasicVals();
 439   const VarDecl *VD = VR->getDecl();
 440
 441   // BasicStore does not model arrays and structs.
 442   if (VD->getType()->isArrayType() || VD->getType()->isStructureOrClassType())
 443     return store;
 444
 445   if (VD->hasGlobalStorage()) {
 446     // Handle variables with global storage: extern, static, PrivateExtern.
 447
 448     // FIXME:: static variables may have an initializer, but the second time a
 449     // function is called those values may not be current. Currently, a function
 450     // will not be called more than once.
 451
 452     // Static global variables should not be visited here.
 453     assert(!(VD->getStorageClass() == SC_Static &&
 454              VD->isFileVarDecl()));
 455
 456     // Process static variables.
 457     if (VD->getStorageClass() == SC_Static) {
 458       // C99: 6.7.8 Initialization
 459       //  If an object that has static storage duration is not initialized
 460       //  explicitly, then:
 461       //   —if it has pointer type, it is initialized to a null pointer;
 462       //   —if it has arithmetic type, it is initialized to (positive or
 463       //     unsigned) zero;
 464       if (!InitVal) {
 465         QualType T = VD->getType();
 466         if (Loc::IsLocType(T))
 467           store = Bind(store, loc::MemRegionVal(VR),
 468                        loc::ConcreteInt(BasicVals.getValue(0, T)));
 469         else if (T->isIntegerType() && T->isScalarType())
 470           store = Bind(store, loc::MemRegionVal(VR),
 471                        nonloc::ConcreteInt(BasicVals.getValue(0, T)));
 472       } else {
 473         store = Bind(store, loc::MemRegionVal(VR), *InitVal);
 474       }
 475     }
 476   } else {
 477     // Process local scalar variables.
 478     QualType T = VD->getType();
 479     // BasicStore only supports scalars.
 480     if ((T->isScalarType() || T->isReferenceType()) &&
 481         svalBuilder.getSymbolManager().canSymbolicate(T)) {
 482       SVal V = InitVal ? *InitVal : UndefinedVal();
 483       store = Bind(store, loc::MemRegionVal(VR), V);
 484     }
 485   }
 486
 487   return store;
 488 }
 489
 490 void BasicStoreManager::print(Store store, llvm::raw_ostream& Out,
 491                               const char* nl, const char *sep) {
 492
 493   BindingsTy B = GetBindings(store);
 494   Out << "Variables:" << nl;
 495
 496   bool isFirst = true;
 497
 498   for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) {
 499     if (isFirst)
 500       isFirst = false;
 501     else
 502       Out << nl;
 503
 504     Out << ' ' << I.getKey() << " : " << I.getData();
 505   }
 506 }
 507
 508
 509 void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) {
 510   BindingsTy B = GetBindings(store);
 511
 512   for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I)
 513     if (!f.HandleBinding(*this, store, I.getKey(), I.getData()))
 514       return;
 515
 516 }
 517
 518 StoreManager::BindingsHandler::~BindingsHandler() {}
 519
 520 //===----------------------------------------------------------------------===//
 521 // Binding invalidation.
 522 //===----------------------------------------------------------------------===//
 523
 524
 525 Store BasicStoreManager::InvalidateRegions(Store store,
 526                                            const MemRegion * const *I,
 527                                            const MemRegion * const *End,
 528                                            const Expr *E, unsigned Count,
 529                                            InvalidatedSymbols *IS,
 530                                            bool invalidateGlobals,
 531                                            InvalidatedRegions *Regions) {
 532   if (invalidateGlobals) {
 533     BindingsTy B = GetBindings(store);
 534     for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) {
 535       const MemRegion *R = I.getKey();
 536       if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
 537         store = InvalidateRegion(store, R, E, Count, IS);
 538     }
 539   }
 540
 541   for ( ; I != End ; ++I) {
 542     const MemRegion *R = *I;
 543     // Don't invalidate globals twice.
 544     if (invalidateGlobals) {
 545       if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
 546         continue;
 547     }
 548     store = InvalidateRegion(store, *I, E, Count, IS);
 549     if (Regions)
 550       Regions->push_back(R);
 551   }
 552
 553   // FIXME: This is copy-and-paste from RegionStore.cpp.
 554   if (invalidateGlobals) {
 555     // Bind the non-static globals memory space to a new symbol that we will
 556     // use to derive the bindings for all non-static globals.
 557     const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion();
 558     SVal V =
 559       svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, E,
 560                                   /* symbol type, doesn't matter */ Ctx.IntTy,
 561                                   Count);
 562
 563     store = Bind(store, loc::MemRegionVal(GS), V);
 564     if (Regions)
 565       Regions->push_back(GS);
 566   }
 567
 568   return store;
 569 }
 570
 571
 572 Store BasicStoreManager::InvalidateRegion(Store store,
 573                                           const MemRegion *R,
 574                                           const Expr *E,
 575                                           unsigned Count,
 576                                           InvalidatedSymbols *IS) {
 577   R = R->StripCasts();
 578
 579   if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
 580       return store;
 581
 582   if (IS) {
 583     BindingsTy B = GetBindings(store);
 584     if (BindingsTy::data_type *Val = B.lookup(R)) {
 585       if (SymbolRef Sym = Val->getAsSymbol())
 586         IS->insert(Sym);
 587     }
 588   }
 589
 590   QualType T = cast<TypedRegion>(R)->getValueType();
 591   SVal V = svalBuilder.getConjuredSymbolVal(R, E, T, Count);
 592   return Bind(store, loc::MemRegionVal(R), V);
 593 }
 594