From b94b81a9ab46c99b00c7ad28c5e1e212c63fc9ac Mon Sep 17 00:00:00 2001 From: Zhongxing Xu Date: Thu, 31 Dec 2009 06:13:07 +0000 Subject: [PATCH] Let constraint manager inform checkers that some assumption logic has happend. Add new states for symbolic regions tracked by malloc checker. This enables us to do malloc checking more accurately. See test case. Based on Lei Zhang's patch and discussion. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@92342 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../clang/Analysis/PathSensitive/Checker.h | 5 +++ .../Analysis/PathSensitive/GRExprEngine.h | 6 ++-- .../clang/Analysis/PathSensitive/GRState.h | 19 +++++++++++ lib/Analysis/GRExprEngine.cpp | 3 +- lib/Analysis/MallocChecker.cpp | 32 ++++++++++++++++--- lib/Analysis/SimpleConstraintManager.cpp | 28 +++++++++++++--- lib/Frontend/AnalysisConsumer.cpp | 4 +-- test/Analysis/malloc.c | 8 +++++ 8 files changed, 91 insertions(+), 14 deletions(-) diff --git a/include/clang/Analysis/PathSensitive/Checker.h b/include/clang/Analysis/PathSensitive/Checker.h index c87889a267..924a8b11b0 100644 --- a/include/clang/Analysis/PathSensitive/Checker.h +++ b/include/clang/Analysis/PathSensitive/Checker.h @@ -269,6 +269,11 @@ public: virtual bool EvalCallExpr(CheckerContext &C, const CallExpr *CE) { return false; } + + virtual const GRState *EvalAssume(const GRState *state, SVal Cond, + bool Assumption) { + return state; + } }; } // end clang namespace diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h index 3f5e16532e..e05c624384 100644 --- a/include/clang/Analysis/PathSensitive/GRExprEngine.h +++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h @@ -80,7 +80,7 @@ class GRExprEngine : public GRSubEngine { typedef llvm::DenseMap CheckerMap; CheckerMap CheckerM; - typedef std::vector >CheckersOrdered; + typedef std::vector > CheckersOrdered; CheckersOrdered Checkers; /// BR - The BugReporter associated with this engine. It is important that @@ -111,10 +111,10 @@ public: GRStmtNodeBuilder &getBuilder() { assert(Builder); return *Builder; } /// setTransferFunctions - void setTransferFunctions(GRTransferFuncs* tf); + void setTransferFunctionsAndCheckers(GRTransferFuncs* tf); void setTransferFunctions(GRTransferFuncs& tf) { - setTransferFunctions(&tf); + setTransferFunctionsAndCheckers(&tf); } /// ViewGraph - Visualize the ExplodedGraph created by executing the diff --git a/include/clang/Analysis/PathSensitive/GRState.h b/include/clang/Analysis/PathSensitive/GRState.h index 421ebbf9bd..424b0d77e8 100644 --- a/include/clang/Analysis/PathSensitive/GRState.h +++ b/include/clang/Analysis/PathSensitive/GRState.h @@ -41,6 +41,7 @@ namespace clang { class GRStateManager; class GRTransferFuncs; +class Checker; typedef ConstraintManager* (*ConstraintManagerCreator)(GRStateManager&); typedef StoreManager* (*StoreManagerCreator)(GRStateManager&); @@ -160,6 +161,9 @@ public: SymbolManager &getSymbolManager() const; GRTransferFuncs &getTransferFuncs() const; + std::vector >::iterator checker_begin() const; + std::vector >::iterator checker_end() const; + //==---------------------------------------------------------------------==// // Constraints on values. //==---------------------------------------------------------------------==// @@ -418,6 +422,9 @@ private: /// for manipulating and creating SVals. GRTransferFuncs* TF; + /// Reference to all checkers in GRExprEngine. + std::vector > *Checkers; + public: GRStateManager(ASTContext& Ctx, @@ -441,6 +448,8 @@ public: GRTransferFuncs& getTransferFuncs() { return *TF; } + std::vector > &getCheckers() { return *Checkers;} + BasicValueFactory &getBasicVals() { return ValueMgr.getBasicValueFactory(); } @@ -697,6 +706,16 @@ inline GRTransferFuncs &GRState::getTransferFuncs() const { return getStateManager().getTransferFuncs(); } +inline std::vector >::iterator +GRState::checker_begin() const { + return getStateManager().getCheckers().begin(); +} + +inline std::vector >::iterator +GRState::checker_end() const { + return getStateManager().getCheckers().end(); +} + template const GRState *GRState::add(typename GRStateTrait::key_type K) const { return getStateManager().add(this, K, get_context()); diff --git a/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp index 2ed35fa469..2ce8edd1cc 100644 --- a/lib/Analysis/GRExprEngine.cpp +++ b/lib/Analysis/GRExprEngine.cpp @@ -330,8 +330,9 @@ GRExprEngine::~GRExprEngine() { // Utility methods. //===----------------------------------------------------------------------===// -void GRExprEngine::setTransferFunctions(GRTransferFuncs* tf) { +void GRExprEngine::setTransferFunctionsAndCheckers(GRTransferFuncs* tf) { StateMgr.TF = tf; + StateMgr.Checkers = &Checkers; tf->RegisterChecks(*this); tf->RegisterPrinters(getStateManager().Printers); } diff --git a/lib/Analysis/MallocChecker.cpp b/lib/Analysis/MallocChecker.cpp index 2ed070a170..fab73ee7b1 100644 --- a/lib/Analysis/MallocChecker.cpp +++ b/lib/Analysis/MallocChecker.cpp @@ -23,13 +23,13 @@ using namespace clang; namespace { class RefState { - enum Kind { Allocated, Released, Escaped } K; + enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped } K; const Stmt *S; public: RefState(Kind k, const Stmt *s) : K(k), S(s) {} - bool isAllocated() const { return K == Allocated; } + bool isAllocated() const { return K == AllocateUnchecked; } bool isReleased() const { return K == Released; } bool isEscaped() const { return K == Escaped; } @@ -37,7 +37,12 @@ public: return K == X.K && S == X.S; } - static RefState getAllocated(const Stmt *s) { return RefState(Allocated, s); } + static RefState getAllocateUnchecked(const Stmt *s) { + return RefState(AllocateUnchecked, s); + } + static RefState getAllocateFailed() { + return RefState(AllocateFailed, 0); + } static RefState getReleased(const Stmt *s) { return RefState(Released, s); } static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); } @@ -62,6 +67,8 @@ public: void EvalDeadSymbols(CheckerContext &C,const Stmt *S,SymbolReaper &SymReaper); void EvalEndPath(GREndPathNodeBuilder &B, void *tag, GRExprEngine &Eng); void PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S); + const GRState *EvalAssume(const GRState *state, SVal Cond, bool Assumption); + private: void MallocMem(CheckerContext &C, const CallExpr *CE); const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE, @@ -74,6 +81,8 @@ private: }; } // end anonymous namespace +typedef llvm::ImmutableMap RegionStateTy; + namespace clang { template <> struct GRStateTrait @@ -144,7 +153,7 @@ const GRState *MallocChecker::MallocMemAux(CheckerContext &C, SymbolRef Sym = RetVal.getAsLocSymbol(); assert(Sym); // Set the symbol's state to Allocated. - return state->set(Sym, RefState::getAllocated(CE)); + return state->set(Sym, RefState::getAllocateUnchecked(CE)); } void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) { @@ -298,3 +307,18 @@ void MallocChecker::PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S) { C.addTransition(state); } + +const GRState *MallocChecker::EvalAssume(const GRState *state, SVal Cond, + bool Assumption) { + // If a symblic region is assumed to NULL, set its state to AllocateFailed. + // FIXME: should also check symbols assumed to non-null. + + RegionStateTy RS = state->get(); + + for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { + if (state->getSymVal(I.getKey())) + state = state->set(I.getKey(),RefState::getAllocateFailed()); + } + + return state; +} diff --git a/lib/Analysis/SimpleConstraintManager.cpp b/lib/Analysis/SimpleConstraintManager.cpp index 015db76080..23c3b41758 100644 --- a/lib/Analysis/SimpleConstraintManager.cpp +++ b/lib/Analysis/SimpleConstraintManager.cpp @@ -15,6 +15,7 @@ #include "SimpleConstraintManager.h" #include "clang/Analysis/PathSensitive/GRExprEngine.h" #include "clang/Analysis/PathSensitive/GRState.h" +#include "clang/Analysis/PathSensitive/Checker.h" namespace clang { @@ -72,8 +73,17 @@ const GRState *SimpleConstraintManager::Assume(const GRState *state, Loc Cond, // EvalAssume is used to call into the GRTransferFunction object to perform // any checker-specific update of the state based on this assumption being // true or false. - return state ? state->getTransferFuncs().EvalAssume(state, Cond, Assumption) - : NULL; + + if (!state) + return 0; + + std::vector >::iterator + I = state->checker_begin(), E = state->checker_end(); + + for (; I != E; ++I) { + state = I->second->EvalAssume(state, Cond, Assumption); + } + return state->getTransferFuncs().EvalAssume(state, Cond, Assumption); } const GRState *SimpleConstraintManager::AssumeAux(const GRState *state, @@ -128,8 +138,18 @@ const GRState *SimpleConstraintManager::Assume(const GRState *state, // EvalAssume is used to call into the GRTransferFunction object to perform // any checker-specific update of the state based on this assumption being // true or false. - return state ? state->getTransferFuncs().EvalAssume(state, Cond, Assumption) - : NULL; + + if (!state) + return 0; + + std::vector >::iterator + I = state->checker_begin(), E = state->checker_end(); + + for (; I != E; ++I) { + state = I->second->EvalAssume(state, Cond, Assumption); + } + + return state->getTransferFuncs().EvalAssume(state, Cond, Assumption); } const GRState *SimpleConstraintManager::AssumeAux(const GRState *state, diff --git a/lib/Frontend/AnalysisConsumer.cpp b/lib/Frontend/AnalysisConsumer.cpp index dd5c6d3013..6824d8f4eb 100644 --- a/lib/Frontend/AnalysisConsumer.cpp +++ b/lib/Frontend/AnalysisConsumer.cpp @@ -373,7 +373,7 @@ static void ActionGRExprEngine(AnalysisConsumer &C, AnalysisManager& mgr, if (C.Opts.EnableExperimentalChecks) RegisterExperimentalChecks(Eng); - Eng.setTransferFunctions(tf); + Eng.setTransferFunctionsAndCheckers(tf); // Set the graph auditor. llvm::OwningPtr Auditor; @@ -506,7 +506,7 @@ static void ActionInlineCall(AnalysisConsumer &C, AnalysisManager &mgr, // Make a fake transfer function. The GRTransferFunc interface will be // removed. - Eng.setTransferFunctions(new GRTransferFuncs()); + Eng.setTransferFunctionsAndCheckers(new GRTransferFuncs()); // Register call inliner as the last checker. RegisterCallInliner(Eng); diff --git a/test/Analysis/malloc.c b/test/Analysis/malloc.c index c885587df7..4d771eeb4b 100644 --- a/test/Analysis/malloc.c +++ b/test/Analysis/malloc.c @@ -43,3 +43,11 @@ int *f5() { q = realloc(q, 20); return q; // no-warning } + +void f6() { + int *p = malloc(10); + if (!p) + return; // no-warning + else + free(p); +} -- 2.40.0