[analyzer] Be less pessimistic about invalidation of global variables

as a result of a call.

Problem:
Global variables, which come in from system libraries should not be
invalidated by all calls. Also, non-system globals should not be
invalidated by system calls.

Solution:
The following solution to invalidation of globals seems flexible enough
for taint (does not invalidate stdin) and should not lead to too
many false positives. We split globals into 3 classes:

* immutable - values are preserved by calls (unless the specific
global is passed in as a parameter):
     A :  Most system globals and const scalars

* invalidated by functions defined in system headers:
     B: errno

* invalidated by all other functions (note, these functions may in
turn contain system calls):
     B: errno
     C: all other globals (which are not in A nor B)

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@147569 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 112 insertions, 34 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
index 7409b19e4e..3877cb88b4 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
@@ -470,13 +470,6 @@ private:
                     const ProgramPointTag *tag, bool isLoad);
 
   bool InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, ExplodedNode *Pred);
-  
-  
-public:
-  /// Returns true if calling the specific function or method would possibly
-  /// cause global variables to be invalidated.
-  bool doesInvalidateGlobals(const CallOrObjCMessage &callOrMessage) const;
-  
 };
 
 } // end ento namespace
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h
index 406cd5a944..b6cf486ec9 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h
@@ -73,12 +73,16 @@ public:
     StackArgumentsSpaceRegionKind,
     HeapSpaceRegionKind,
     UnknownSpaceRegionKind,
-    NonStaticGlobalSpaceRegionKind,
     StaticGlobalSpaceRegionKind,
-    BEG_GLOBAL_MEMSPACES = NonStaticGlobalSpaceRegionKind,
-    END_GLOBAL_MEMSPACES = StaticGlobalSpaceRegionKind,
+    GlobalInternalSpaceRegionKind,
+    GlobalSystemSpaceRegionKind,
+    GlobalImmutableSpaceRegionKind,
+    BEG_NON_STATIC_GLOBAL_MEMSPACES = GlobalInternalSpaceRegionKind,
+    END_NON_STATIC_GLOBAL_MEMSPACES = GlobalImmutableSpaceRegionKind,
+    BEG_GLOBAL_MEMSPACES = StaticGlobalSpaceRegionKind,
+    END_GLOBAL_MEMSPACES = GlobalImmutableSpaceRegionKind,
     BEG_MEMSPACES = GenericMemSpaceRegionKind,
-    END_MEMSPACES = StaticGlobalSpaceRegionKind,
+    END_MEMSPACES = GlobalImmutableSpaceRegionKind,
     // Untyped regions.
     SymbolicRegionKind,
     AllocaRegionKind,
@@ -150,7 +154,7 @@ public:
   static bool classof(const MemRegion*) { return true; }
 };
 
-/// MemSpaceRegion - A memory region that represents and "memory space";
+/// MemSpaceRegion - A memory region that represents a "memory space";
 ///  for example, the set of global variables, the stack frame, etc.
 class MemSpaceRegion : public MemRegion {
 protected:
@@ -187,7 +191,11 @@ public:
     return k >= BEG_GLOBAL_MEMSPACES && k <= END_GLOBAL_MEMSPACES;
   }
 };
-  
+
+/// \class The region of the static variables within the current CodeTextRegion
+/// scope.
+/// Currently, only the static locals are placed there, so we know that these
+/// variables do not get invalidated by calls to other functions.
 class StaticGlobalSpaceRegion : public GlobalsSpaceRegion {
   friend class MemRegionManager;
 
@@ -207,22 +215,86 @@ public:
     return R->getKind() == StaticGlobalSpaceRegionKind;
   }
 };
-  
+
+/// \class The region for all the non-static global variables.
+///
+/// This class is further split into subclasses for efficient implementation of
+/// invalidating a set of related global values as is done in
+/// RegionStoreManager::invalidateRegions (instead of finding all the dependent
+/// globals, we invalidate the whole parent region).
 class NonStaticGlobalSpaceRegion : public GlobalsSpaceRegion {
   friend class MemRegionManager;
   
-  NonStaticGlobalSpaceRegion(MemRegionManager *mgr)
-    : GlobalsSpaceRegion(mgr, NonStaticGlobalSpaceRegionKind) {}
+protected:
+  NonStaticGlobalSpaceRegion(MemRegionManager *mgr, Kind k)
+    : GlobalsSpaceRegion(mgr, k) {}
   
 public:
 
   void dumpToStream(raw_ostream &os) const;
 
   static bool classof(const MemRegion *R) {
-    return R->getKind() == NonStaticGlobalSpaceRegionKind;
+    Kind k = R->getKind();
+    return k >= BEG_NON_STATIC_GLOBAL_MEMSPACES &&
+           k <= END_NON_STATIC_GLOBAL_MEMSPACES;
   }
 };
-  
+
+/// \class The region containing globals which are defined in system/external
+/// headers and are considered modifiable by system calls (ex: errno).
+class GlobalSystemSpaceRegion : public NonStaticGlobalSpaceRegion {
+  friend class MemRegionManager;
+
+  GlobalSystemSpaceRegion(MemRegionManager *mgr)
+    : NonStaticGlobalSpaceRegion(mgr, GlobalSystemSpaceRegionKind) {}
+
+public:
+
+  void dumpToStream(raw_ostream &os) const;
+
+  static bool classof(const MemRegion *R) {
+    return R->getKind() == GlobalSystemSpaceRegionKind;
+  }
+};
+
+/// \class The region containing globals which are considered not to be modified
+/// or point to data which could be modified as a result of a function call
+/// (system or internal). Ex: Const global scalars would be modeled as part of
+/// this region. This region also includes most system globals since they have
+/// low chance of being modified.
+class GlobalImmutableSpaceRegion : public NonStaticGlobalSpaceRegion {
+  friend class MemRegionManager;
+
+  GlobalImmutableSpaceRegion(MemRegionManager *mgr)
+    : NonStaticGlobalSpaceRegion(mgr, GlobalImmutableSpaceRegionKind) {}
+
+public:
+
+  void dumpToStream(raw_ostream &os) const;
+
+  static bool classof(const MemRegion *R) {
+    return R->getKind() == GlobalImmutableSpaceRegionKind;
+  }
+};
+
+/// \class The region containing globals which can be modified by calls to
+/// "internally" defined functions - (for now just) functions other then system
+/// calls.
+class GlobalInternalSpaceRegion : public NonStaticGlobalSpaceRegion {
+  friend class MemRegionManager;
+
+  GlobalInternalSpaceRegion(MemRegionManager *mgr)
+    : NonStaticGlobalSpaceRegion(mgr, GlobalInternalSpaceRegionKind) {}
+
+public:
+
+  void dumpToStream(raw_ostream &os) const;
+
+  static bool classof(const MemRegion *R) {
+    return R->getKind() == GlobalInternalSpaceRegionKind;
+  }
+};
+
 class HeapSpaceRegion : public MemSpaceRegion {
   virtual void anchor();
   friend class MemRegionManager;
@@ -927,7 +999,10 @@ class MemRegionManager {
   llvm::BumpPtrAllocator& A;
   llvm::FoldingSet<MemRegion> Regions;
 
-  NonStaticGlobalSpaceRegion *globals;
+  GlobalInternalSpaceRegion *InternalGlobals;
+  GlobalSystemSpaceRegion *SystemGlobals;
+  GlobalImmutableSpaceRegion *ImmutableGlobals;
+
   
   llvm::DenseMap<const StackFrameContext *, StackLocalsSpaceRegion *> 
     StackLocalsSpaceRegions;
@@ -942,7 +1017,8 @@ class MemRegionManager {
 
 public:
   MemRegionManager(ASTContext &c, llvm::BumpPtrAllocator& a)
-    : C(c), A(a), globals(0), heap(0), unknown(0), code(0) {}
+    : C(c), A(a), InternalGlobals(0), SystemGlobals(0), ImmutableGlobals(0),
+      heap(0), unknown(0), code(0) {}
 
   ~MemRegionManager();
 
@@ -962,7 +1038,9 @@ public:
 
   /// getGlobalsRegion - Retrieve the memory region associated with
   ///  global variables.
-  const GlobalsSpaceRegion *getGlobalsRegion(const CodeTextRegion *R = 0);
+  const GlobalsSpaceRegion *getGlobalsRegion(
+      MemRegion::Kind K = MemRegion::GlobalInternalSpaceRegionKind,
+      const CodeTextRegion *R = 0);
 
   /// getHeapRegion - Retrieve the memory region associated with the
   ///  generic "heap".
@@ -1059,11 +1137,6 @@ public:
   const BlockDataRegion *getBlockDataRegion(const BlockTextRegion *bc,
                                             const LocationContext *lc = NULL);
 
-  bool isGlobalsRegion(const MemRegion* R) {
-    assert(R);
-    return R == globals;
-  }
-  
 private:
   template <typename RegionTy, typename A1>
   RegionTy* getRegion(const A1 a1);
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h
index ed589f9c44..500f587e85 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h
@@ -19,6 +19,7 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/AST/ExprObjC.h"
 #include "clang/AST/ExprCXX.h"
+#include "clang/Basic/SourceManager.h"
 #include "llvm/ADT/PointerUnion.h"
 
 namespace clang {
@@ -233,6 +234,16 @@ public:
     return ActualCallE && isa<CXXMemberCallExpr>(ActualCallE);
   }
 
+  /// Check if the callee is declared in the system header.
+  bool isInSystemHeader() const {
+    if (const Decl *FD = getDecl()) {
+      const SourceManager &SM =
+        State->getStateManager().getContext().getSourceManager();
+      return SM.isInSystemHeader(FD->getLocation());
+    }
+    return false;
+  }
+
   const Expr *getOriginExpr() const {
     if (!CallE)
       return Msg.getOriginExpr();
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
index 700a26505b..e9d6d6ec96 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
@@ -34,8 +34,8 @@ class ASTContext;
 
 namespace ento {
 
+class CallOrObjCMessage;
 class ProgramStateManager;
-
 typedef ConstraintManager* (*ConstraintManagerCreator)(ProgramStateManager&,
                                                        SubEngine&);
 typedef StoreManager* (*StoreManagerCreator)(ProgramStateManager&);
@@ -219,9 +219,9 @@ public:
   ///  cleared from the store. The regions are provided as a continuous array
   ///  from Begin to End. Optionally invalidates global regions as well.
   const ProgramState *invalidateRegions(ArrayRef<const MemRegion *> Regions,
-                                   const Expr *E, unsigned BlockCount,
-                                   StoreManager::InvalidatedSymbols *IS = 0,
-                                   bool invalidateGlobals = false) const;
+                               const Expr *E, unsigned BlockCount,
+                               StoreManager::InvalidatedSymbols *IS = 0,
+                               const CallOrObjCMessage *Call = 0) const;
 
   /// enterStackFrame - Returns the state for entry to the given stack frame,
   ///  preserving the current state.
@@ -384,7 +384,7 @@ private:
   invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions,
                         const Expr *E, unsigned BlockCount,
                         StoreManager::InvalidatedSymbols &IS,
-                        bool invalidateGlobals) const;
+                        const CallOrObjCMessage *Call) const;
 };
 
 class ProgramStateSet {
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
index e7835dbab8..87586ae2aa 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
@@ -29,6 +29,7 @@ class StackFrameContext;
 
 namespace ento {
 
+class CallOrObjCMessage;
 class ProgramState;
 class ProgramStateManager;
 class SubRegionMap;
@@ -180,8 +181,8 @@ public:
   ///   symbols to mark the values of invalidated regions.
   /// \param[in,out] IS A set to fill with any symbols that are no longer
   ///   accessible. Pass \c NULL if this information will not be used.
-  /// \param[in] invalidateGlobals If \c true, any non-static global regions
-  ///   are invalidated as well.
+  /// \param[in] Call The call expression which will be used to determine which
+  ///   globals should get invalidated.
   /// \param[in,out] Regions A vector to fill with any regions being
   ///   invalidated. This should include any regions explicitly invalidated
   ///   even if they do not currently have bindings. Pass \c NULL if this
@@ -190,7 +191,7 @@ public:
                                      ArrayRef<const MemRegion *> Regions,
                                      const Expr *E, unsigned Count,
                                      InvalidatedSymbols &IS,
-                                     bool invalidateGlobals,
+                                     const CallOrObjCMessage *Call,
                                      InvalidatedRegions *Invalidated) = 0;
 
   /// enterStackFrame - Let the StoreManager to do something when execution