After a lengthy design discussion, add support for "ownership attributes" for malloc/free checking. Patch by Andrew McGregor!

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

1 files changed, 156 insertions, 17 deletions

diff --git a/lib/Checker/MallocChecker.cpp b/lib/Checker/MallocChecker.cpp
index dcc21ca386..4ed309513e 100644
--- a/lib/Checker/MallocChecker.cpp
+++ b/lib/Checker/MallocChecker.cpp
@@ -24,15 +24,17 @@ using namespace clang;
 namespace {
 
 class RefState {
-  enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped } K;
+  enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped, Relinquished } K;
   const Stmt *S;
 
 public:
   RefState(Kind k, const Stmt *s) : K(k), S(s) {}
 
   bool isAllocated() const { return K == AllocateUnchecked; }
+  bool isFailed() const { return K == AllocateFailed; }
   bool isReleased() const { return K == Released; }
   bool isEscaped() const { return K == Escaped; }
+  bool isRelinquished() const { return K == Relinquished; }
 
   bool operator==(const RefState &X) const {
     return K == X.K && S == X.S;
@@ -46,6 +48,7 @@ public:
   }
   static RefState getReleased(const Stmt *s) { return RefState(Released, s); }
   static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); }
+  static RefState getRelinquished(const Stmt *s) { return RefState(Relinquished, s); }
 
   void Profile(llvm::FoldingSetNodeID &ID) const {
     ID.AddInteger(K);
@@ -59,12 +62,13 @@ class MallocChecker : public CheckerVisitor<MallocChecker> {
   BuiltinBug *BT_DoubleFree;
   BuiltinBug *BT_Leak;
   BuiltinBug *BT_UseFree;
+  BuiltinBug *BT_UseRelinquished;
   BuiltinBug *BT_BadFree;
   IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc;
 
 public:
   MallocChecker() 
-    : BT_DoubleFree(0), BT_Leak(0), BT_UseFree(0), BT_BadFree(0),
+    : BT_DoubleFree(0), BT_Leak(0), BT_UseFree(0), BT_UseRelinquished(0), BT_BadFree(0),
       II_malloc(0), II_free(0), II_realloc(0), II_calloc(0) {}
   static void *getTag();
   bool EvalCallExpr(CheckerContext &C, const CallExpr *CE);
@@ -73,9 +77,13 @@ public:
   void PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S);
   const GRState *EvalAssume(const GRState *state, SVal Cond, bool Assumption);
   void VisitLocation(CheckerContext &C, const Stmt *S, SVal l);
+  virtual void PreVisitBind(CheckerContext &C, const Stmt *AssignE,
+                            const Stmt *StoreE, SVal location,
+                            SVal val);
 
 private:
   void MallocMem(CheckerContext &C, const CallExpr *CE);
+  void MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE, const OwnershipAttr* Att);
   const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE,
                               const Expr *SizeEx, SVal Init,
                               const GRState *state) {
@@ -86,8 +94,9 @@ private:
                               const GRState *state);
 
   void FreeMem(CheckerContext &C, const CallExpr *CE);
+  void FreeMemAttr(CheckerContext &C, const CallExpr *CE, const OwnershipAttr* Att);
   const GRState *FreeMemAux(CheckerContext &C, const CallExpr *CE,
-                            const GRState *state);
+                            const GRState *state, unsigned Num, bool Hold);
 
   void ReallocMem(CheckerContext &C, const CallExpr *CE);
   void CallocMem(CheckerContext &C, const CallExpr *CE);
@@ -156,7 +165,31 @@ bool MallocChecker::EvalCallExpr(CheckerContext &C, const CallExpr *CE) {
     return true;
   }
 
-  return false;
+  // Check all the attributes, if there are any.
+  // There can be multiple of these attributes.
+  bool rv = false;
+  if (FD->hasAttrs()) {
+    for (const Attr *attr = FD->getAttrs(); attr; attr = attr->getNext()) {
+      if(const OwnershipAttr* Att = dyn_cast<OwnershipAttr>(attr)) {
+        switch (Att->getKind()) {
+        case OwnershipAttr::Returns: {
+          MallocMemReturnsAttr(C, CE, Att);
+          rv = true;
+          break;
+        }
+        case OwnershipAttr::Takes:
+        case OwnershipAttr::Holds: {
+          FreeMemAttr(C, CE, Att);
+          rv = true;
+          break;
+        }
+        default:
+          break;
+        }
+      }
+    }
+  }
+  return rv;
 }
 
 void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) {
@@ -165,6 +198,23 @@ void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) {
   C.addTransition(state);
 }
 
+void MallocChecker::MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
+                                         const OwnershipAttr* Att) {
+  if (!Att->isModule("malloc"))
+    return;
+
+  const unsigned *I = Att->begin(), *E = Att->end();
+  if (I != E) {
+    const GRState *state =
+        MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
+    C.addTransition(state);
+    return;
+  }
+  const GRState *state = MallocMemAux(C, CE, UnknownVal(), UndefinedVal(),
+                                        C.getState());
+  C.addTransition(state);
+}
+
 const GRState *MallocChecker::MallocMemAux(CheckerContext &C,  
                                            const CallExpr *CE,
                                            SVal Size, SVal Init,
@@ -196,25 +246,52 @@ const GRState *MallocChecker::MallocMemAux(CheckerContext &C,
 }
 
 void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) {
-  const GRState *state = FreeMemAux(C, CE, C.getState());
+  const GRState *state = FreeMemAux(C, CE, C.getState(), 0, false);
 
   if (state)
     C.addTransition(state);
 }
 
+void MallocChecker::FreeMemAttr(CheckerContext &C, const CallExpr *CE,
+                                     const OwnershipAttr* Att) {
+  if (!Att->isModule("malloc"))
+    return;
+
+  for (const unsigned *I = Att->begin(), *E = Att->end(); I != E; ++I) {
+    const GRState *state =
+        FreeMemAux(C, CE, C.getState(), *I, Att->isKind(OwnershipAttr::Holds));
+  if (state)
+    C.addTransition(state);
+  }
+}
+
 const GRState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE,
-                                         const GRState *state) {
-  const Expr *ArgExpr = CE->getArg(0);
+                                         const GRState *state, unsigned Num,
+                                         bool Hold) {
+  const Expr *ArgExpr = CE->getArg(Num);
   SVal ArgVal = state->getSVal(ArgExpr);
 
-  // If ptr is NULL, no operation is preformed.
-  if (ArgVal.isZeroConstant())
+  DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal);
+
+  // Check for null dereferences.
+  if (!isa<Loc>(location))
     return state;
-  
+
+  // FIXME: Technically using 'Assume' here can result in a path
+  //  bifurcation.  In such cases we need to return two states, not just one.
+  const GRState *notNullState, *nullState;
+  llvm::tie(notNullState, nullState) = state->Assume(location);
+
+  // The explicit NULL case, no operation is performed.
+  if (nullState && !notNullState)
+    return nullState;
+
+  assert(notNullState);
+
   // Unknown values could easily be okay
   // Undefined values are handled elsewhere
   if (ArgVal.isUnknownOrUndef())
-    return state;
+    return notNullState;
 
   const MemRegion *R = ArgVal.getAsRegion();
   
@@ -253,7 +330,7 @@ const GRState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE,
   // Various cases could lead to non-symbol values here.
   // For now, ignore them.
   if (!SR)
-    return state;
+    return notNullState;
 
   SymbolRef Sym = SR->getSymbol();
   
@@ -263,14 +340,15 @@ const GRState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE,
   // called on a pointer that does not get its pointee directly from malloc(). 
   // Full support of this requires inter-procedural analysis.
   if (!RS)
-    return state;
+    return notNullState;
 
   // Check double free.
   if (RS->isReleased()) {
     ExplodedNode *N = C.GenerateSink();
     if (N) {
       if (!BT_DoubleFree)
-        BT_DoubleFree = new BuiltinBug("Double free",
+        BT_DoubleFree
+          = new BuiltinBug("Double free",
                          "Try to free a memory block that has been released");
       // FIXME: should find where it's freed last time.
       BugReport *R = new BugReport(*BT_DoubleFree, 
@@ -281,7 +359,9 @@ const GRState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE,
   }
 
   // Normal free.
-  return state->set<RegionState>(Sym, RefState::getReleased(CE));
+  if (Hold)
+    return notNullState->set<RegionState>(Sym, RefState::getRelinquished(CE));
+  return notNullState->set<RegionState>(Sym, RefState::getReleased(CE));
 }
 
 bool MallocChecker::SummarizeValue(llvm::raw_ostream& os, SVal V) {
@@ -446,13 +526,13 @@ void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) {
                                       ValMgr.makeIntValWithPtrWidth(0, false));
 
     if (const GRState *stateSizeZero = stateNotEqual->Assume(SizeZero, true)) {
-      const GRState *stateFree = FreeMemAux(C, CE, stateSizeZero);
+      const GRState *stateFree = FreeMemAux(C, CE, stateSizeZero, 0, false);
       if (stateFree)
         C.addTransition(stateFree->BindExpr(CE, UndefinedVal(), true));
     }
 
     if (const GRState *stateSizeNotZero=stateNotEqual->Assume(SizeZero,false)) {
-      const GRState *stateFree = FreeMemAux(C, CE, stateSizeNotZero);
+      const GRState *stateFree = FreeMemAux(C, CE, stateSizeNotZero, 0, false);
       if (stateFree) {
         // FIXME: We should copy the content of the original buffer.
         const GRState *stateRealloc = MallocMemAux(C, CE, CE->getArg(1), 
@@ -581,3 +661,62 @@ void MallocChecker::VisitLocation(CheckerContext &C, const Stmt *S, SVal l) {
       }
   }
 }
+
+void MallocChecker::PreVisitBind(CheckerContext &C,
+                                 const Stmt *AssignE,
+                                 const Stmt *StoreE,
+                                 SVal location,
+                                 SVal val) {
+  // The PreVisitBind implements the same algorithm as already used by the 
+  // Objective C ownership checker: if the pointer escaped from this scope by 
+  // assignment, let it go.  However, assigning to fields of a stack-storage 
+  // structure does not transfer ownership.
+
+  const GRState *state = C.getState();
+  DefinedOrUnknownSVal l = cast<DefinedOrUnknownSVal>(location);
+
+  // Check for null dereferences.
+  if (!isa<Loc>(l))
+    return;
+
+  // Before checking if the state is null, check if 'val' has a RefState.
+  // Only then should we check for null and bifurcate the state.
+  SymbolRef Sym = val.getLocSymbolInBase();
+  if (Sym) {
+    if (const RefState *RS = state->get<RegionState>(Sym)) {
+      // If ptr is NULL, no operation is performed.
+      const GRState *notNullState, *nullState;
+      llvm::tie(notNullState, nullState) = state->Assume(l);
+
+      // Generate a transition for 'nullState' to record the assumption
+      // that the state was null.
+      if (nullState)
+        C.addTransition(nullState);
+
+      if (!notNullState)
+        return;
+
+      if (RS->isAllocated()) {
+        // Something we presently own is being assigned somewhere.
+        const MemRegion *AR = location.getAsRegion();
+        if (!AR)
+          return;
+        AR = AR->StripCasts()->getBaseRegion();
+        do {
+          // If it is on the stack, we still own it.
+          if (AR->hasStackNonParametersStorage())
+            break;
+
+          // If the state can't represent this binding, we still own it.
+          if (notNullState == (notNullState->bindLoc(cast<Loc>(location), UnknownVal())))
+            break;
+
+          // We no longer own this pointer.
+          notNullState = notNullState->set<RegionState>(Sym, RefState::getRelinquished(StoreE));
+        }
+        while (false);
+      }
+      C.addTransition(notNullState);
+    }
+  }
+}