lib/StaticAnalyzer/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::ObjCPropRefKind:
 200     case loc::ConcreteIntKind:
 201       // Support direct accesses to memory.  It's up to individual checkers
 202       // to flag an error.
 203       return UnknownVal();
 204
 205     default:
 206       assert (false && "Invalid Loc.");
 207       break;
 208   }
 209
 210   return UnknownVal();
 211 }
 212
 213 Store BasicStoreManager::Bind(Store store, Loc loc, SVal V) {
 214   if (isa<loc::ConcreteInt>(loc))
 215     return store;
 216
 217   const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
 218
 219   // Special case: a default symbol assigned to the NonStaticGlobalsSpaceRegion
 220   //  that is used to derive other symbols.
 221   if (isa<NonStaticGlobalSpaceRegion>(R)) {
 222     BindingsTy B = GetBindings(store);
 223     return VBFactory.add(B, R, V).getRoot();
 224   }
 225
 226   // Special case: handle store of pointer values (Loc) to pointers via
 227   // a cast to intXX_t*, void*, etc.  This is needed to handle
 228   // OSCompareAndSwap32Barrier/OSCompareAndSwap64Barrier.
 229   if (isa<Loc>(V) || isa<nonloc::LocAsInteger>(V))
 230     if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
 231       // FIXME: Should check for index 0.
 232       QualType T = ER->getLocationType();
 233
 234       if (isHigherOrderRawPtr(T, Ctx))
 235         R = ER->getSuperRegion();
 236     }
 237
 238   if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) || isa<CXXThisRegion>(R)))
 239     return store;
 240
 241   const TypedRegion *TyR = cast<TypedRegion>(R);
 242
 243   // Do not bind to arrays.  We need to explicitly check for this so that
 244   // we do not encounter any weirdness of trying to load/store from arrays.
 245   if (TyR->isBoundable() && TyR->getValueType()->isArrayType())
 246     return store;
 247
 248   if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&V)) {
 249     // Only convert 'V' to a location iff the underlying region type
 250     // is a location as well.
 251     // FIXME: We are allowing a store of an arbitrary location to
 252     // a pointer.  We may wish to flag a type error here if the types
 253     // are incompatible.  This may also cause lots of breakage
 254     // elsewhere. Food for thought.
 255     if (TyR->isBoundable() && Loc::IsLocType(TyR->getValueType()))
 256       V = X->getLoc();
 257   }
 258
 259   BindingsTy B = GetBindings(store);
 260   return V.isUnknown()
 261     ? VBFactory.remove(B, R).getRoot()
 262     : VBFactory.add(B, R, V).getRoot();
 263 }
 264
 265 Store BasicStoreManager::Remove(Store store, Loc loc) {
 266   switch (loc.getSubKind()) {
 267     case loc::MemRegionKind: {
 268       const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
 269
 270       if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
 271           isa<CXXThisRegion>(R)))
 272         return store;
 273
 274       return VBFactory.remove(GetBindings(store), R).getRoot();
 275     }
 276     default:
 277       assert ("Remove for given Loc type not yet implemented.");
 278       return store;
 279   }
 280 }
 281
 282 Store BasicStoreManager::removeDeadBindings(Store store,
 283                                             const StackFrameContext *LCtx,
 284                                             SymbolReaper& SymReaper,
 285                            llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
 286 {
 287   BindingsTy B = GetBindings(store);
 288   typedef SVal::symbol_iterator symbol_iterator;
 289
 290   // Iterate over the variable bindings.
 291   for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
 292     if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) {
 293       if (SymReaper.isLive(VR))
 294         RegionRoots.push_back(VR);
 295       else
 296         continue;
 297     }
 298     else if (isa<ObjCIvarRegion>(I.getKey()) ||
 299              isa<NonStaticGlobalSpaceRegion>(I.getKey()) ||
 300              isa<CXXThisRegion>(I.getKey()))
 301       RegionRoots.push_back(I.getKey());
 302     else
 303       continue;
 304
 305     // Mark the bindings in the data as live.
 306     SVal X = I.getData();
 307     for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
 308       SymReaper.markLive(*SI);
 309   }
 310
 311   // Scan for live variables and live symbols.
 312   llvm::SmallPtrSet<const MemRegion*, 10> Marked;
 313
 314   while (!RegionRoots.empty()) {
 315     const MemRegion* MR = RegionRoots.back();
 316     RegionRoots.pop_back();
 317
 318     while (MR) {
 319       if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) {
 320         SymReaper.markLive(SymR->getSymbol());
 321         break;
 322       }
 323       else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR) ||
 324                isa<NonStaticGlobalSpaceRegion>(MR) || isa<CXXThisRegion>(MR)) {
 325         if (Marked.count(MR))
 326           break;
 327
 328         Marked.insert(MR);
 329         SVal X = Retrieve(store, loc::MemRegionVal(MR));
 330
 331         // FIXME: We need to handle symbols nested in region definitions.
 332         for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
 333           SymReaper.markLive(*SI);
 334
 335         if (!isa<loc::MemRegionVal>(X))
 336           break;
 337
 338         const loc::MemRegionVal& LVD = cast<loc::MemRegionVal>(X);
 339         RegionRoots.push_back(LVD.getRegion());
 340         break;
 341       }
 342       else if (const SubRegion* R = dyn_cast<SubRegion>(MR))
 343         MR = R->getSuperRegion();
 344       else
 345         break;
 346     }
 347   }
 348
 349   // Remove dead variable bindings.
 350   for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
 351     const MemRegion* R = I.getKey();
 352
 353     if (!Marked.count(R)) {
 354       store = Remove(store, svalBuilder.makeLoc(R));
 355       SVal X = I.getData();
 356
 357       for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
 358         SymReaper.maybeDead(*SI);
 359     }
 360   }
 361
 362   return store;
 363 }
 364
 365 Store BasicStoreManager::scanForIvars(Stmt *B, const Decl* SelfDecl,
 366                                       const MemRegion *SelfRegion, Store St) {
 367   for (Stmt::child_iterator CI=B->child_begin(), CE=B->child_end();
 368        CI != CE; ++CI) {
 369
 370     if (!*CI)
 371       continue;
 372
 373     // Check if the statement is an ivar reference.  We only
 374     // care about self.ivar.
 375     if (ObjCIvarRefExpr *IV = dyn_cast<ObjCIvarRefExpr>(*CI)) {
 376       const Expr *Base = IV->getBase()->IgnoreParenCasts();
 377       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Base)) {
 378         if (DR->getDecl() == SelfDecl) {
 379           const ObjCIvarRegion *IVR = MRMgr.getObjCIvarRegion(IV->getDecl(),
 380                                                          SelfRegion);
 381           SVal X = svalBuilder.getRegionValueSymbolVal(IVR);
 382           St = Bind(St, svalBuilder.makeLoc(IVR), X);
 383         }
 384       }
 385     }
 386     else
 387       St = scanForIvars(*CI, SelfDecl, SelfRegion, St);
 388   }
 389
 390   return St;
 391 }
 392
 393 Store BasicStoreManager::getInitialStore(const LocationContext *InitLoc) {
 394   // The LiveVariables information already has a compilation of all VarDecls
 395   // used in the function.  Iterate through this set, and "symbolicate"
 396   // any VarDecl whose value originally comes from outside the function.
 397   typedef LiveVariables::AnalysisDataTy LVDataTy;
 398   LVDataTy& D = InitLoc->getLiveVariables()->getAnalysisData();
 399   Store St = VBFactory.getEmptyMap().getRoot();
 400
 401   for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
 402     const NamedDecl* ND = I->first;
 403
 404     // Handle implicit parameters.
 405     if (const ImplicitParamDecl* PD = dyn_cast<ImplicitParamDecl>(ND)) {
 406       const Decl& CD = *InitLoc->getDecl();
 407       if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(&CD)) {
 408         if (MD->getSelfDecl() == PD) {
 409           // FIXME: Add type constraints (when they become available) to
 410           // SelfRegion?  (i.e., it implements MD->getClassInterface()).
 411           const VarRegion *VR = MRMgr.getVarRegion(PD, InitLoc);
 412           const MemRegion *SelfRegion =
 413             svalBuilder.getRegionValueSymbolVal(VR).getAsRegion();
 414           assert(SelfRegion);
 415           St = Bind(St, svalBuilder.makeLoc(VR), loc::MemRegionVal(SelfRegion));
 416           // Scan the method for ivar references.  While this requires an
 417           // entire AST scan, the cost should not be high in practice.
 418           St = scanForIvars(MD->getBody(), PD, SelfRegion, St);
 419         }
 420       }
 421     }
 422   }
 423
 424   if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(InitLoc->getDecl())) {
 425     // For C++ methods add symbolic region for 'this' in initial stack frame.
 426     QualType ThisT = MD->getThisType(StateMgr.getContext());
 427     MemRegionManager &RegMgr = svalBuilder.getRegionManager();
 428     const CXXThisRegion *ThisR = RegMgr.getCXXThisRegion(ThisT, InitLoc);
 429     SVal ThisV = svalBuilder.getRegionValueSymbolVal(ThisR);
 430     St = Bind(St, svalBuilder.makeLoc(ThisR), ThisV);
 431   }
 432
 433   return St;
 434 }
 435
 436 Store BasicStoreManager::BindDeclInternal(Store store, const VarRegion* VR,
 437                                           SVal* InitVal) {
 438
 439   BasicValueFactory& BasicVals = StateMgr.getBasicVals();
 440   const VarDecl *VD = VR->getDecl();
 441
 442   // BasicStore does not model arrays and structs.
 443   if (VD->getType()->isArrayType() || VD->getType()->isStructureOrClassType())
 444     return store;
 445
 446   if (VD->hasGlobalStorage()) {
 447     // Handle variables with global storage: extern, static, PrivateExtern.
 448
 449     // FIXME:: static variables may have an initializer, but the second time a
 450     // function is called those values may not be current. Currently, a function
 451     // will not be called more than once.
 452
 453     // Static global variables should not be visited here.
 454     assert(!(VD->getStorageClass() == SC_Static &&
 455              VD->isFileVarDecl()));
 456
 457     // Process static variables.
 458     if (VD->getStorageClass() == SC_Static) {
 459       // C99: 6.7.8 Initialization
 460       //  If an object that has static storage duration is not initialized
 461       //  explicitly, then:
 462       //   -if it has pointer type, it is initialized to a null pointer;
 463       //   -if it has arithmetic type, it is initialized to (positive or
 464       //     unsigned) zero;
 465       if (!InitVal) {
 466         QualType T = VD->getType();
 467         if (Loc::IsLocType(T))
 468           store = Bind(store, loc::MemRegionVal(VR),
 469                        loc::ConcreteInt(BasicVals.getValue(0, T)));
 470         else if (T->isIntegerType() && T->isScalarType())
 471           store = Bind(store, loc::MemRegionVal(VR),
 472                        nonloc::ConcreteInt(BasicVals.getValue(0, T)));
 473       } else {
 474         store = Bind(store, loc::MemRegionVal(VR), *InitVal);
 475       }
 476     }
 477   } else {
 478     // Process local scalar variables.
 479     QualType T = VD->getType();
 480     // BasicStore only supports scalars.
 481     if ((T->isScalarType() || T->isReferenceType()) &&
 482         svalBuilder.getSymbolManager().canSymbolicate(T)) {
 483       SVal V = InitVal ? *InitVal : UndefinedVal();
 484       store = Bind(store, loc::MemRegionVal(VR), V);
 485     }
 486   }
 487
 488   return store;
 489 }
 490
 491 void BasicStoreManager::print(Store store, llvm::raw_ostream& Out,
 492                               const char* nl, const char *sep) {
 493
 494   BindingsTy B = GetBindings(store);
 495   Out << "Variables:" << nl;
 496
 497   bool isFirst = true;
 498
 499   for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) {
 500     if (isFirst)
 501       isFirst = false;
 502     else
 503       Out << nl;
 504
 505     Out << ' ' << I.getKey() << " : " << I.getData();
 506   }
 507 }
 508
 509
 510 void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) {
 511   BindingsTy B = GetBindings(store);
 512
 513   for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I)
 514     if (!f.HandleBinding(*this, store, I.getKey(), I.getData()))
 515       return;
 516
 517 }
 518
 519 StoreManager::BindingsHandler::~BindingsHandler() {}
 520
 521 //===----------------------------------------------------------------------===//
 522 // Binding invalidation.
 523 //===----------------------------------------------------------------------===//
 524
 525
 526 Store BasicStoreManager::InvalidateRegions(Store store,
 527                                            const MemRegion * const *I,
 528                                            const MemRegion * const *End,
 529                                            const Expr *E, unsigned Count,
 530                                            InvalidatedSymbols *IS,
 531                                            bool invalidateGlobals,
 532                                            InvalidatedRegions *Regions) {
 533   if (invalidateGlobals) {
 534     BindingsTy B = GetBindings(store);
 535     for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) {
 536       const MemRegion *R = I.getKey();
 537       if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
 538         store = InvalidateRegion(store, R, E, Count, IS);
 539     }
 540   }
 541
 542   for ( ; I != End ; ++I) {
 543     const MemRegion *R = *I;
 544     // Don't invalidate globals twice.
 545     if (invalidateGlobals) {
 546       if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
 547         continue;
 548     }
 549     store = InvalidateRegion(store, *I, E, Count, IS);
 550     if (Regions)
 551       Regions->push_back(R);
 552   }
 553
 554   // FIXME: This is copy-and-paste from RegionStore.cpp.
 555   if (invalidateGlobals) {
 556     // Bind the non-static globals memory space to a new symbol that we will
 557     // use to derive the bindings for all non-static globals.
 558     const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion();
 559     SVal V =
 560       svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, E,
 561                                   /* symbol type, doesn't matter */ Ctx.IntTy,
 562                                   Count);
 563
 564     store = Bind(store, loc::MemRegionVal(GS), V);
 565     if (Regions)
 566       Regions->push_back(GS);
 567   }
 568
 569   return store;
 570 }
 571
 572
 573 Store BasicStoreManager::InvalidateRegion(Store store,
 574                                           const MemRegion *R,
 575                                           const Expr *E,
 576                                           unsigned Count,
 577                                           InvalidatedSymbols *IS) {
 578   R = R->StripCasts();
 579
 580   if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
 581       return store;
 582
 583   if (IS) {
 584     BindingsTy B = GetBindings(store);
 585     if (BindingsTy::data_type *Val = B.lookup(R)) {
 586       if (SymbolRef Sym = Val->getAsSymbol())
 587         IS->insert(Sym);
 588     }
 589   }
 590
 591   QualType T = cast<TypedRegion>(R)->getValueType();
 592   SVal V = svalBuilder.getConjuredSymbolVal(R, E, T, Count);
 593   return Bind(store, loc::MemRegionVal(R), V);
 594 }