[analyzer] Malloc checker: rework realloc handling:

1) Support the case when realloc fails to reduce False Positives. (We
essentially need to restore the state of the pointer being reallocated.)

2) Realloc behaves differently under special conditions (from pointer is
null, size is 0). When detecting these cases, we should consider
under-constrained states (size might or might not be 0). The
old version handled this in a very hacky way. The code did not
differentiate between definite and possible (no consideration for
under-constrained states). Further, after processing each special case,
the realloc processing function did not return but chained to the next
special case processing. So you could end up in an execution in which
you first see the states in which size is 0 and realloc ~ free(),
followed by the states corresponding to size is not 0 followed by the
evaluation of the regular realloc behavior.

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

1 files changed, 80 insertions, 34 deletions

diff --git a/lib/StaticAnalyzer/Checkers/MallocChecker.cpp b/lib/StaticAnalyzer/Checkers/MallocChecker.cpp
index f486a7e8c9..98298c850b 100644
--- a/lib/StaticAnalyzer/Checkers/MallocChecker.cpp
+++ b/lib/StaticAnalyzer/Checkers/MallocChecker.cpp
@@ -42,6 +42,7 @@ public:
   bool isReleased() const { return K == Released; }
   //bool isEscaped() const { return K == Escaped; }
   //bool isRelinquished() const { return K == Relinquished; }
+  const Stmt *getStmt() const { return S; }
 
   bool operator==(const RefState &X) const {
     return K == X.K && S == X.S;
@@ -65,8 +66,6 @@ public:
   }
 };
 
-class RegionState {};
-
 class MallocChecker : public Checker<check::DeadSymbols,
                                      check::EndPath,
                                      check::PreStmt<ReturnStmt>,
@@ -188,7 +187,9 @@ private:
 } // end anonymous namespace
 
 typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
-
+typedef llvm::ImmutableMap<SymbolRef, SymbolRef> SymRefToSymRefTy;
+class RegionState {};
+class ReallocPairs {};
 namespace clang {
 namespace ento {
   template <>
@@ -196,6 +197,12 @@ namespace ento {
     : public ProgramStatePartialTrait<RegionStateTy> {
     static void *GDMIndex() { static int x; return &x; }
   };
+
+  template <>
+  struct ProgramStateTrait<ReallocPairs>
+    : public ProgramStatePartialTrait<SymRefToSymRefTy> {
+    static void *GDMIndex() { static int x; return &x; }
+  };
 }
 }
 
@@ -642,43 +649,55 @@ void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) const {
     svalBuilder.evalEQ(state, Arg1Val,
                        svalBuilder.makeIntValWithPtrWidth(0, false));
 
+  ProgramStateRef StatePtrIsNull, StatePtrNotNull;
+  llvm::tie(StatePtrIsNull, StatePtrNotNull) = state->assume(PtrEQ);
+  ProgramStateRef StateSizeIsZero, StateSizeNotZero;
+  llvm::tie(StateSizeIsZero, StateSizeNotZero) = state->assume(SizeZero);
+  // We only assume exceptional states if they are definitely true; if the
+  // state is under-constrained, assume regular realloc behavior.
+  bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull;
+  bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero;
+
   // If the ptr is NULL and the size is not 0, the call is equivalent to 
   // malloc(size).
-  ProgramStateRef stateEqual = state->assume(PtrEQ, true);
-  if (stateEqual && state->assume(SizeZero, false)) {
-    // Hack: set the NULL symbolic region to released to suppress false warning.
-    // In the future we should add more states for allocated regions, e.g., 
-    // CheckedNull, CheckedNonNull.
-    
-    SymbolRef Sym = arg0Val.getAsLocSymbol();
-    if (Sym)
-      stateEqual = stateEqual->set<RegionState>(Sym, RefState::getReleased(CE));
-
+  if ( PrtIsNull && !SizeIsZero) {
     ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1), 
-                                              UndefinedVal(), stateEqual);
+                                               UndefinedVal(), StatePtrIsNull);
     C.addTransition(stateMalloc);
+    return;
   }
 
-  if (ProgramStateRef stateNotEqual = state->assume(PtrEQ, false)) {
-    // If the size is 0, free the memory.
-    if (ProgramStateRef stateSizeZero =
-          stateNotEqual->assume(SizeZero, true))
-      if (ProgramStateRef stateFree = 
-          FreeMemAux(C, CE, stateSizeZero, 0, false)) {
+  if (PrtIsNull && SizeIsZero)
+    return;
 
-        // Bind the return value to NULL because it is now free.
-        C.addTransition(stateFree->BindExpr(CE, LCtx,
-                                            svalBuilder.makeNull(), true));
-      }
-    if (ProgramStateRef stateSizeNotZero =
-          stateNotEqual->assume(SizeZero,false))
-      if (ProgramStateRef stateFree = FreeMemAux(C, CE, stateSizeNotZero,
-                                                0, false)) {
-        // FIXME: We should copy the content of the original buffer.
-        ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1), 
-                                                   UnknownVal(), stateFree);
-        C.addTransition(stateRealloc);
-      }
+  assert(!PrtIsNull);
+
+  // If the size is 0, free the memory.
+  if (SizeIsZero)
+    if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero,0,false)){
+      // Bind the return value to NULL because it is now free.
+      // TODO: This is tricky. Does not currently work.
+      // The semantics of the return value are:
+      // If size was equal to 0, either NULL or a pointer suitable to be passed
+      // to free() is returned.
+      C.addTransition(stateFree->BindExpr(CE, LCtx,
+          svalBuilder.makeNull(), true));
+      return;
+    }
+
+  // Default behavior.
+  if (ProgramStateRef stateFree = FreeMemAux(C, CE, state, 0, false)) {
+    // FIXME: We should copy the content of the original buffer.
+    ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
+                                                UnknownVal(), stateFree);
+    SymbolRef FromPtr = arg0Val.getAsSymbol();
+    SVal RetVal = state->getSVal(CE, LCtx);
+    SymbolRef ToPtr = RetVal.getAsSymbol();
+    if (!stateRealloc || !FromPtr || !ToPtr)
+      return;
+    stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr, FromPtr);
+    C.addTransition(stateRealloc);
+    return;
   }
 }
 
@@ -738,6 +757,14 @@ void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
     }
   }
   
+  // Cleanup the Realloc Pairs Map.
+  SymRefToSymRefTy RP = state->get<ReallocPairs>();
+  for (SymRefToSymRefTy::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
+    if (SymReaper.isDead(I->first) || SymReaper.isDead(I->second)) {
+      state = state->remove<ReallocPairs>(I->first);
+    }
+  }
+
   ExplodedNode *N = C.addTransition(state->set<RegionState>(RS));
 
   if (N && generateReport) {
@@ -871,7 +898,6 @@ ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state,
                                               SVal Cond,
                                               bool Assumption) const {
   RegionStateTy RS = state->get<RegionState>();
-
   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
     // If the symbol is assumed to NULL or another constant, this will
     // return an APSInt*.
@@ -879,6 +905,26 @@ ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state,
       state = state->remove<RegionState>(I.getKey());
   }
 
+  // Realloc returns 0 when reallocation fails, which means that we should
+  // restore the state of the pointer being reallocated.
+  SymRefToSymRefTy RP = state->get<ReallocPairs>();
+  for (SymRefToSymRefTy::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
+    // If the symbol is assumed to NULL or another constant, this will
+    // return an APSInt*.
+    if (state->getSymVal(I.getKey())) {
+      const RefState *RS = state->get<RegionState>(I.getData());
+      if (RS) {
+        if (RS->isReleased())
+          state = state->set<RegionState>(I.getData(),
+                             RefState::getAllocateUnchecked(RS->getStmt()));
+        if (RS->isAllocated())
+          state = state->set<RegionState>(I.getData(),
+                             RefState::getReleased(RS->getStmt()));
+      }
+      state = state->remove<ReallocPairs>(I.getKey());
+    }
+  }
+
   return state;
 }