[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

3 files changed, 107 insertions, 47 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h
index dca18926fb..d02eab77c8 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h
@@ -195,8 +195,7 @@ private:
                                  bool MarkAsSink,
                                  ExplodedNode *P = 0,
                                  const ProgramPointTag *Tag = 0) {
-    assert(State);
-    if (State == Pred->getState() && !Tag && !MarkAsSink)
+    if (!State || (State == Pred->getState() && !Tag && !MarkAsSink))
       return Pred;
 
     Changed = true;
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;
 }
 
diff --git a/test/Analysis/malloc.c b/test/Analysis/malloc.c
index 0321f523a3..d1d850c681 100644
--- a/test/Analysis/malloc.c
+++ b/test/Analysis/malloc.c
@@ -32,6 +32,32 @@ void f2_realloc_1() {
   int *q = realloc(p,0); // no-warning
 }
 
+void reallocNotNullPtr(unsigned sizeIn) {
+  unsigned size = 12;
+  char *p = (char*)malloc(size);
+  if (p) {
+    char *q = (char*)realloc(p, sizeIn);
+    char x = *q; // expected-warning {{Allocated memory never released.}}
+  }
+}
+
+int *realloctest1() {
+  int *q = malloc(12);
+  q = realloc(q, 20);
+  return q; // no warning - returning the allocated value
+}
+
+// p should be freed if realloc fails.
+void reallocFails() {
+  char *p = malloc(12);
+  char *r = realloc(p, 12+1);
+  if (!r) {
+    free(p);
+  } else {
+    free(r);
+  }
+}
+
 // This case tests that storing malloc'ed memory to a static variable which is
 // then returned is not leaked.  In the absence of known contracts for functions
 // or inter-procedural analysis, this is a conservative answer.
@@ -391,17 +417,6 @@ void doNotInvalidateWhenPassedToSystemCalls(char *s) {
 
 // Below are the known false positives.
 
-// TODO: There should be no warning here.
-void reallocFails(int *g, int f) {
-  char *p = malloc(12);
-  char *r = realloc(p, 12+1);
-  if (!r) {
-    free(p); // expected-warning {{Try to free a memory block that has been released}}
-  } else {
-    free(r);
-  }
-}
-
 // TODO: There should be no warning here. This one might be difficult to get rid of.
 void dependsOnValueOfPtr(int *g, unsigned f) {
   int *p;