diff options
Diffstat (limited to 'lib/Checker')
45 files changed, 5169 insertions, 1013 deletions
diff --git a/lib/Checker/AnalysisConsumer.cpp b/lib/Checker/AnalysisConsumer.cpp new file mode 100644 index 000000000000..524f37e39662 --- /dev/null +++ b/lib/Checker/AnalysisConsumer.cpp @@ -0,0 +1,592 @@ +//===--- AnalysisConsumer.cpp - ASTConsumer for running Analyses ----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// "Meta" ASTConsumer for running different source analyses. +// +//===----------------------------------------------------------------------===// + +#include "clang/Checker/AnalysisConsumer.h" +#include "clang/AST/ASTConsumer.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/DeclObjC.h" +#include "clang/AST/ParentMap.h" +#include "clang/Analysis/Analyses/LiveVariables.h" +#include "clang/Analysis/Analyses/UninitializedValues.h" +#include "clang/Analysis/CFG.h" +#include "clang/Checker/Checkers/LocalCheckers.h" +#include "clang/Checker/ManagerRegistry.h" +#include "clang/Checker/BugReporter/PathDiagnostic.h" +#include "clang/Checker/PathSensitive/AnalysisManager.h" +#include "clang/Checker/BugReporter/BugReporter.h" +#include "clang/Checker/PathSensitive/GRExprEngine.h" +#include "clang/Checker/PathSensitive/GRTransferFuncs.h" +#include "clang/Checker/PathDiagnosticClients.h" +#include "GRExprEngineExperimentalChecks.h" +#include "clang/Basic/FileManager.h" +#include "clang/Basic/SourceManager.h" +#include "clang/Frontend/AnalyzerOptions.h" +#include "clang/Lex/Preprocessor.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/System/Path.h" +#include "llvm/System/Program.h" +#include "llvm/ADT/OwningPtr.h" + +using namespace clang; + +static ExplodedNode::Auditor* CreateUbiViz(); + +//===----------------------------------------------------------------------===// +// Special PathDiagnosticClients. +//===----------------------------------------------------------------------===// + +static PathDiagnosticClient* +CreatePlistHTMLDiagnosticClient(const std::string& prefix, + const Preprocessor &PP) { + llvm::sys::Path F(prefix); + PathDiagnosticClient *PD = CreateHTMLDiagnosticClient(F.getDirname(), PP); + return CreatePlistDiagnosticClient(prefix, PP, PD); +} + +//===----------------------------------------------------------------------===// +// AnalysisConsumer declaration. +//===----------------------------------------------------------------------===// + +namespace { + +class AnalysisConsumer : public ASTConsumer { +public: + typedef void (*CodeAction)(AnalysisConsumer &C, AnalysisManager &M, Decl *D); + typedef void (*TUAction)(AnalysisConsumer &C, AnalysisManager &M, + TranslationUnitDecl &TU); + +private: + typedef std::vector<CodeAction> Actions; + typedef std::vector<TUAction> TUActions; + + Actions FunctionActions; + Actions ObjCMethodActions; + Actions ObjCImplementationActions; + Actions CXXMethodActions; + TUActions TranslationUnitActions; // Remove this. + +public: + ASTContext* Ctx; + const Preprocessor &PP; + const std::string OutDir; + AnalyzerOptions Opts; + + // PD is owned by AnalysisManager. + PathDiagnosticClient *PD; + + StoreManagerCreator CreateStoreMgr; + ConstraintManagerCreator CreateConstraintMgr; + + llvm::OwningPtr<AnalysisManager> Mgr; + + AnalysisConsumer(const Preprocessor& pp, + const std::string& outdir, + const AnalyzerOptions& opts) + : Ctx(0), PP(pp), OutDir(outdir), + Opts(opts), PD(0) { + DigestAnalyzerOptions(); + } + + void DigestAnalyzerOptions() { + // Create the PathDiagnosticClient. + if (!OutDir.empty()) { + switch (Opts.AnalysisDiagOpt) { + default: +#define ANALYSIS_DIAGNOSTICS(NAME, CMDFLAG, DESC, CREATEFN, AUTOCREATE) \ + case PD_##NAME: PD = CREATEFN(OutDir, PP); break; +#include "clang/Frontend/Analyses.def" + } + } + + // Create the analyzer component creators. + if (ManagerRegistry::StoreMgrCreator != 0) { + CreateStoreMgr = ManagerRegistry::StoreMgrCreator; + } + else { + switch (Opts.AnalysisStoreOpt) { + default: + assert(0 && "Unknown store manager."); +#define ANALYSIS_STORE(NAME, CMDFLAG, DESC, CREATEFN) \ + case NAME##Model: CreateStoreMgr = CREATEFN; break; +#include "clang/Frontend/Analyses.def" + } + } + + if (ManagerRegistry::ConstraintMgrCreator != 0) + CreateConstraintMgr = ManagerRegistry::ConstraintMgrCreator; + else { + switch (Opts.AnalysisConstraintsOpt) { + default: + assert(0 && "Unknown store manager."); +#define ANALYSIS_CONSTRAINTS(NAME, CMDFLAG, DESC, CREATEFN) \ + case NAME##Model: CreateConstraintMgr = CREATEFN; break; +#include "clang/Frontend/Analyses.def" + } + } + } + + void DisplayFunction(const Decl *D) { + if (!Opts.AnalyzerDisplayProgress) + return; + + SourceManager &SM = Mgr->getASTContext().getSourceManager(); + PresumedLoc Loc = SM.getPresumedLoc(D->getLocation()); + llvm::errs() << "ANALYZE: " << Loc.getFilename(); + + if (isa<FunctionDecl>(D) || isa<ObjCMethodDecl>(D)) { + const NamedDecl *ND = cast<NamedDecl>(D); + llvm::errs() << ' ' << ND << '\n'; + } + else if (isa<BlockDecl>(D)) { + llvm::errs() << ' ' << "block(line:" << Loc.getLine() << ",col:" + << Loc.getColumn() << '\n'; + } + } + + void addCodeAction(CodeAction action) { + FunctionActions.push_back(action); + ObjCMethodActions.push_back(action); + CXXMethodActions.push_back(action); + } + + void addTranslationUnitAction(TUAction action) { + TranslationUnitActions.push_back(action); + } + + void addObjCImplementationAction(CodeAction action) { + ObjCImplementationActions.push_back(action); + } + + virtual void Initialize(ASTContext &Context) { + Ctx = &Context; + Mgr.reset(new AnalysisManager(*Ctx, PP.getDiagnostics(), + PP.getLangOptions(), PD, + CreateStoreMgr, CreateConstraintMgr, + Opts.MaxNodes, Opts.MaxLoop, + Opts.VisualizeEGDot, Opts.VisualizeEGUbi, + Opts.PurgeDead, Opts.EagerlyAssume, + Opts.TrimGraph, Opts.InlineCall)); + } + + virtual void HandleTranslationUnit(ASTContext &C); + void HandleCode(Decl *D, Actions& actions); +}; +} // end anonymous namespace + +//===----------------------------------------------------------------------===// +// AnalysisConsumer implementation. +//===----------------------------------------------------------------------===// + +void AnalysisConsumer::HandleTranslationUnit(ASTContext &C) { + + TranslationUnitDecl *TU = C.getTranslationUnitDecl(); + + for (DeclContext::decl_iterator I = TU->decls_begin(), E = TU->decls_end(); + I != E; ++I) { + Decl *D = *I; + + switch (D->getKind()) { + case Decl::CXXConstructor: + case Decl::CXXDestructor: + case Decl::CXXConversion: + case Decl::CXXMethod: + case Decl::Function: { + FunctionDecl* FD = cast<FunctionDecl>(D); + + if (FD->isThisDeclarationADefinition()) { + if (!Opts.AnalyzeSpecificFunction.empty() && + FD->getDeclName().getAsString() != Opts.AnalyzeSpecificFunction) + break; + DisplayFunction(FD); + HandleCode(FD, FunctionActions); + } + break; + } + + case Decl::ObjCMethod: { + ObjCMethodDecl* MD = cast<ObjCMethodDecl>(D); + + if (MD->isThisDeclarationADefinition()) { + if (!Opts.AnalyzeSpecificFunction.empty() && + Opts.AnalyzeSpecificFunction != MD->getSelector().getAsString()) + break; + DisplayFunction(MD); + HandleCode(MD, ObjCMethodActions); + } + break; + } + + case Decl::ObjCImplementation: { + ObjCImplementationDecl* ID = cast<ObjCImplementationDecl>(*I); + HandleCode(ID, ObjCImplementationActions); + + for (ObjCImplementationDecl::method_iterator MI = ID->meth_begin(), + ME = ID->meth_end(); MI != ME; ++MI) { + if ((*MI)->isThisDeclarationADefinition()) { + if (!Opts.AnalyzeSpecificFunction.empty() && + Opts.AnalyzeSpecificFunction != (*MI)->getSelector().getAsString()) + break; + HandleCode(*MI, ObjCMethodActions); + } + } + break; + } + + default: + break; + } + } + + for (TUActions::iterator I = TranslationUnitActions.begin(), + E = TranslationUnitActions.end(); I != E; ++I) { + (*I)(*this, *Mgr, *TU); + } + + // Explicitly destroy the PathDiagnosticClient. This will flush its output. + // FIXME: This should be replaced with something that doesn't rely on + // side-effects in PathDiagnosticClient's destructor. This is required when + // used with option -disable-free. + Mgr.reset(NULL); +} + +static void FindBlocks(DeclContext *D, llvm::SmallVectorImpl<Decl*> &WL) { + if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) + WL.push_back(BD); + + for (DeclContext::decl_iterator I = D->decls_begin(), E = D->decls_end(); + I!=E; ++I) + if (DeclContext *DC = dyn_cast<DeclContext>(*I)) + FindBlocks(DC, WL); +} + +void AnalysisConsumer::HandleCode(Decl *D, Actions& actions) { + + // Don't run the actions if an error has occured with parsing the file. + Diagnostic &Diags = PP.getDiagnostics(); + if (Diags.hasErrorOccurred() || Diags.hasFatalErrorOccurred()) + return; + + // Don't run the actions on declarations in header files unless + // otherwise specified. + SourceManager &SM = Ctx->getSourceManager(); + SourceLocation SL = SM.getInstantiationLoc(D->getLocation()); + if (!Opts.AnalyzeAll && !SM.isFromMainFile(SL)) + return; + + // Clear the AnalysisManager of old AnalysisContexts. + Mgr->ClearContexts(); + + // Dispatch on the actions. + llvm::SmallVector<Decl*, 10> WL; + WL.push_back(D); + + if (D->hasBody() && Opts.AnalyzeNestedBlocks) + FindBlocks(cast<DeclContext>(D), WL); + + for (Actions::iterator I = actions.begin(), E = actions.end(); I != E; ++I) + for (llvm::SmallVectorImpl<Decl*>::iterator WI=WL.begin(), WE=WL.end(); + WI != WE; ++WI) + (*I)(*this, *Mgr, *WI); +} + +//===----------------------------------------------------------------------===// +// Analyses +//===----------------------------------------------------------------------===// + +static void ActionWarnDeadStores(AnalysisConsumer &C, AnalysisManager& mgr, + Decl *D) { + if (LiveVariables *L = mgr.getLiveVariables(D)) { + BugReporter BR(mgr); + CheckDeadStores(*mgr.getCFG(D), *L, mgr.getParentMap(D), BR); + } +} + +static void ActionWarnUninitVals(AnalysisConsumer &C, AnalysisManager& mgr, + Decl *D) { + if (CFG* c = mgr.getCFG(D)) { + CheckUninitializedValues(*c, mgr.getASTContext(), mgr.getDiagnostic()); + } +} + + +static void ActionGRExprEngine(AnalysisConsumer &C, AnalysisManager& mgr, + Decl *D, + GRTransferFuncs* tf) { + + llvm::OwningPtr<GRTransferFuncs> TF(tf); + + // Construct the analysis engine. We first query for the LiveVariables + // information to see if the CFG is valid. + // FIXME: Inter-procedural analysis will need to handle invalid CFGs. + if (!mgr.getLiveVariables(D)) + return; + GRExprEngine Eng(mgr, TF.take()); + + if (C.Opts.EnableExperimentalInternalChecks) + RegisterExperimentalInternalChecks(Eng); + + RegisterAppleChecks(Eng, *D); + + if (C.Opts.EnableExperimentalChecks) + RegisterExperimentalChecks(Eng); + + if (C.Opts.EnableIdempotentOperationChecker) + RegisterIdempotentOperationChecker(Eng); + + // Set the graph auditor. + llvm::OwningPtr<ExplodedNode::Auditor> Auditor; + if (mgr.shouldVisualizeUbigraph()) { + Auditor.reset(CreateUbiViz()); + ExplodedNode::SetAuditor(Auditor.get()); + } + + // Execute the worklist algorithm. + Eng.ExecuteWorkList(mgr.getStackFrame(D), mgr.getMaxNodes()); + + // Release the auditor (if any) so that it doesn't monitor the graph + // created BugReporter. + ExplodedNode::SetAuditor(0); + + // Visualize the exploded graph. + if (mgr.shouldVisualizeGraphviz()) + Eng.ViewGraph(mgr.shouldTrimGraph()); + + // Display warnings. + Eng.getBugReporter().FlushReports(); +} + +static void ActionObjCMemCheckerAux(AnalysisConsumer &C, AnalysisManager& mgr, + Decl *D, bool GCEnabled) { + + GRTransferFuncs* TF = MakeCFRefCountTF(mgr.getASTContext(), + GCEnabled, + mgr.getLangOptions()); + + ActionGRExprEngine(C, mgr, D, TF); +} + +static void ActionObjCMemChecker(AnalysisConsumer &C, AnalysisManager& mgr, + Decl *D) { + + switch (mgr.getLangOptions().getGCMode()) { + default: + assert (false && "Invalid GC mode."); + case LangOptions::NonGC: + ActionObjCMemCheckerAux(C, mgr, D, false); + break; + + case LangOptions::GCOnly: + ActionObjCMemCheckerAux(C, mgr, D, true); + break; + + case LangOptions::HybridGC: + ActionObjCMemCheckerAux(C, mgr, D, false); + ActionObjCMemCheckerAux(C, mgr, D, true); + break; + } +} + +static void ActionDisplayLiveVariables(AnalysisConsumer &C, + AnalysisManager& mgr, Decl *D) { + if (LiveVariables* L = mgr.getLiveVariables(D)) { + L->dumpBlockLiveness(mgr.getSourceManager()); + } +} + +static void ActionCFGDump(AnalysisConsumer &C, AnalysisManager& mgr, Decl *D) { + if (CFG *cfg = mgr.getCFG(D)) { + cfg->dump(mgr.getLangOptions()); + } +} + +static void ActionCFGView(AnalysisConsumer &C, AnalysisManager& mgr, Decl *D) { + if (CFG *cfg = mgr.getCFG(D)) { + cfg->viewCFG(mgr.getLangOptions()); + } +} + +static void ActionSecuritySyntacticChecks(AnalysisConsumer &C, + AnalysisManager &mgr, Decl *D) { + BugReporter BR(mgr); + CheckSecuritySyntaxOnly(D, BR); +} + +static void ActionLLVMConventionChecker(AnalysisConsumer &C, + AnalysisManager &mgr, + TranslationUnitDecl &TU) { + BugReporter BR(mgr); + CheckLLVMConventions(TU, BR); +} + +static void ActionWarnObjCDealloc(AnalysisConsumer &C, AnalysisManager& mgr, + Decl *D) { + if (mgr.getLangOptions().getGCMode() == LangOptions::GCOnly) + return; + BugReporter BR(mgr); + CheckObjCDealloc(cast<ObjCImplementationDecl>(D), mgr.getLangOptions(), BR); +} + +static void ActionWarnObjCUnusedIvars(AnalysisConsumer &C, AnalysisManager& mgr, + Decl *D) { + BugReporter BR(mgr); + CheckObjCUnusedIvar(cast<ObjCImplementationDecl>(D), BR); +} + +static void ActionWarnObjCMethSigs(AnalysisConsumer &C, AnalysisManager& mgr, + Decl *D) { + BugReporter BR(mgr); + CheckObjCInstMethSignature(cast<ObjCImplementationDecl>(D), BR); +} + +static void ActionWarnSizeofPointer(AnalysisConsumer &C, AnalysisManager &mgr, + Decl *D) { + BugReporter BR(mgr); + CheckSizeofPointer(D, BR); +} + +//===----------------------------------------------------------------------===// +// AnalysisConsumer creation. +//===----------------------------------------------------------------------===// + +ASTConsumer* clang::CreateAnalysisConsumer(const Preprocessor& pp, + const std::string& OutDir, + const AnalyzerOptions& Opts) { + llvm::OwningPtr<AnalysisConsumer> C(new AnalysisConsumer(pp, OutDir, Opts)); + + for (unsigned i = 0; i < Opts.AnalysisList.size(); ++i) + switch (Opts.AnalysisList[i]) { +#define ANALYSIS(NAME, CMD, DESC, SCOPE)\ + case NAME:\ + C->add ## SCOPE ## Action(&Action ## NAME);\ + break; +#include "clang/Frontend/Analyses.def" + default: break; + } + + // Last, disable the effects of '-Werror' when using the AnalysisConsumer. + pp.getDiagnostics().setWarningsAsErrors(false); + + return C.take(); +} + +//===----------------------------------------------------------------------===// +// Ubigraph Visualization. FIXME: Move to separate file. +//===----------------------------------------------------------------------===// + +namespace { + +class UbigraphViz : public ExplodedNode::Auditor { + llvm::OwningPtr<llvm::raw_ostream> Out; + llvm::sys::Path Dir, Filename; + unsigned Cntr; + + typedef llvm::DenseMap<void*,unsigned> VMap; + VMap M; + +public: + UbigraphViz(llvm::raw_ostream* out, llvm::sys::Path& dir, + llvm::sys::Path& filename); + + ~UbigraphViz(); + + virtual void AddEdge(ExplodedNode* Src, ExplodedNode* Dst); +}; + +} // end anonymous namespace + +static ExplodedNode::Auditor* CreateUbiViz() { + std::string ErrMsg; + + llvm::sys::Path Dir = llvm::sys::Path::GetTemporaryDirectory(&ErrMsg); + if (!ErrMsg.empty()) + return 0; + + llvm::sys::Path Filename = Dir; + Filename.appendComponent("llvm_ubi"); + Filename.makeUnique(true,&ErrMsg); + + if (!ErrMsg.empty()) + return 0; + + llvm::errs() << "Writing '" << Filename.str() << "'.\n"; + + llvm::OwningPtr<llvm::raw_fd_ostream> Stream; + Stream.reset(new llvm::raw_fd_ostream(Filename.c_str(), ErrMsg)); + + if (!ErrMsg.empty()) + return 0; + + return new UbigraphViz(Stream.take(), Dir, Filename); +} + +void UbigraphViz::AddEdge(ExplodedNode* Src, ExplodedNode* Dst) { + + assert (Src != Dst && "Self-edges are not allowed."); + + // Lookup the Src. If it is a new node, it's a root. + VMap::iterator SrcI= M.find(Src); + unsigned SrcID; + + if (SrcI == M.end()) { + M[Src] = SrcID = Cntr++; + *Out << "('vertex', " << SrcID << ", ('color','#00ff00'))\n"; + } + else + SrcID = SrcI->second; + + // Lookup the Dst. + VMap::iterator DstI= M.find(Dst); + unsigned DstID; + + if (DstI == M.end()) { + M[Dst] = DstID = Cntr++; + *Out << "('vertex', " << DstID << ")\n"; + } + else { + // We have hit DstID before. Change its style to reflect a cache hit. + DstID = DstI->second; + *Out << "('change_vertex_style', " << DstID << ", 1)\n"; + } + + // Add the edge. + *Out << "('edge', " << SrcID << ", " << DstID + << ", ('arrow','true'), ('oriented', 'true'))\n"; +} + +UbigraphViz::UbigraphViz(llvm::raw_ostream* out, llvm::sys::Path& dir, + llvm::sys::Path& filename) + : Out(out), Dir(dir), Filename(filename), Cntr(0) { + + *Out << "('vertex_style_attribute', 0, ('shape', 'icosahedron'))\n"; + *Out << "('vertex_style', 1, 0, ('shape', 'sphere'), ('color', '#ffcc66')," + " ('size', '1.5'))\n"; +} + +UbigraphViz::~UbigraphViz() { + Out.reset(0); + llvm::errs() << "Running 'ubiviz' program... "; + std::string ErrMsg; + llvm::sys::Path Ubiviz = llvm::sys::Program::FindProgramByName("ubiviz"); + std::vector<const char*> args; + args.push_back(Ubiviz.c_str()); + args.push_back(Filename.c_str()); + args.push_back(0); + + if (llvm::sys::Program::ExecuteAndWait(Ubiviz, &args[0],0,0,0,0,&ErrMsg)) { + llvm::errs() << "Error viewing graph: " << ErrMsg << "\n"; + } + + // Delete the directory. + Dir.eraseFromDisk(true); +} diff --git a/lib/Checker/AttrNonNullChecker.cpp b/lib/Checker/AttrNonNullChecker.cpp index 309a74ce544b..d0bccb27b405 100644 --- a/lib/Checker/AttrNonNullChecker.cpp +++ b/lib/Checker/AttrNonNullChecker.cpp @@ -60,9 +60,10 @@ void AttrNonNullChecker::PreVisitCallExpr(CheckerContext &C, if (!Att->isNonNull(idx)) continue; - const SVal &V = state->getSVal(*I); - const DefinedSVal *DV = dyn_cast<DefinedSVal>(&V); + SVal V = state->getSVal(*I); + DefinedSVal *DV = dyn_cast<DefinedSVal>(&V); + // If the value is unknown or undefined, we can't perform this check. if (!DV) continue; diff --git a/lib/Checker/BasicConstraintManager.cpp b/lib/Checker/BasicConstraintManager.cpp index e89546ecb018..eee5c5946674 100644 --- a/lib/Checker/BasicConstraintManager.cpp +++ b/lib/Checker/BasicConstraintManager.cpp @@ -54,22 +54,28 @@ public: ISetFactory(statemgr.getAllocator()) {} const GRState* AssumeSymNE(const GRState* state, SymbolRef sym, - const llvm::APSInt& V); + const llvm::APSInt& V, + const llvm::APSInt& Adjustment); const GRState* AssumeSymEQ(const GRState* state, SymbolRef sym, - const llvm::APSInt& V); + const llvm::APSInt& V, + const llvm::APSInt& Adjustment); const GRState* AssumeSymLT(const GRState* state, SymbolRef sym, - const llvm::APSInt& V); + const llvm::APSInt& V, + const llvm::APSInt& Adjustment); const GRState* AssumeSymGT(const GRState* state, SymbolRef sym, - const llvm::APSInt& V); + const llvm::APSInt& V, + const llvm::APSInt& Adjustment); const GRState* AssumeSymGE(const GRState* state, SymbolRef sym, - const llvm::APSInt& V); + const llvm::APSInt& V, + const llvm::APSInt& Adjustment); const GRState* AssumeSymLE(const GRState* state, SymbolRef sym, - const llvm::APSInt& V); + const llvm::APSInt& V, + const llvm::APSInt& Adjustment); const GRState* AddEQ(const GRState* state, SymbolRef sym, const llvm::APSInt& V); @@ -94,46 +100,52 @@ ConstraintManager* clang::CreateBasicConstraintManager(GRStateManager& statemgr, return new BasicConstraintManager(statemgr, subengine); } + const GRState* BasicConstraintManager::AssumeSymNE(const GRState *state, SymbolRef sym, - const llvm::APSInt& V) { - // First, determine if sym == X, where X != V. + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) { + // First, determine if sym == X, where X+Adjustment != V. + llvm::APSInt Adjusted = V-Adjustment; if (const llvm::APSInt* X = getSymVal(state, sym)) { - bool isFeasible = (*X != V); + bool isFeasible = (*X != Adjusted); return isFeasible ? state : NULL; } - // Second, determine if sym != V. - if (isNotEqual(state, sym, V)) + // Second, determine if sym+Adjustment != V. + if (isNotEqual(state, sym, Adjusted)) return state; // If we reach here, sym is not a constant and we don't know if it is != V. // Make that assumption. - return AddNE(state, sym, V); + return AddNE(state, sym, Adjusted); } -const GRState *BasicConstraintManager::AssumeSymEQ(const GRState *state, - SymbolRef sym, - const llvm::APSInt &V) { - // First, determine if sym == X, where X != V. +const GRState* +BasicConstraintManager::AssumeSymEQ(const GRState *state, SymbolRef sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) { + // First, determine if sym == X, where X+Adjustment != V. + llvm::APSInt Adjusted = V-Adjustment; if (const llvm::APSInt* X = getSymVal(state, sym)) { - bool isFeasible = *X == V; + bool isFeasible = (*X == Adjusted); return isFeasible ? state : NULL; } - // Second, determine if sym != V. - if (isNotEqual(state, sym, V)) + // Second, determine if sym+Adjustment != V. + if (isNotEqual(state, sym, Adjusted)) return NULL; // If we reach here, sym is not a constant and we don't know if it is == V. // Make that assumption. - return AddEQ(state, sym, V); + return AddEQ(state, sym, Adjusted); } -// These logic will be handled in another ConstraintManager. -const GRState *BasicConstraintManager::AssumeSymLT(const GRState *state, - SymbolRef sym, - const llvm::APSInt& V) { +// The logic for these will be handled in another ConstraintManager. +const GRState* +BasicConstraintManager::AssumeSymLT(const GRState *state, SymbolRef sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) { // Is 'V' the smallest possible value? if (V == llvm::APSInt::getMinValue(V.getBitWidth(), V.isUnsigned())) { // sym cannot be any value less than 'V'. This path is infeasible. @@ -141,13 +153,13 @@ const GRState *BasicConstraintManager::AssumeSymLT(const GRState *state, } // FIXME: For now have assuming x < y be the same as assuming sym != V; - return AssumeSymNE(state, sym, V); + return AssumeSymNE(state, sym, V, Adjustment); } -const GRState *BasicConstraintManager::AssumeSymGT(const GRState *state, - SymbolRef sym, - const llvm::APSInt& V) { - +const GRState* +BasicConstraintManager::AssumeSymGT(const GRState *state, SymbolRef sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) { // Is 'V' the largest possible value? if (V == llvm::APSInt::getMaxValue(V.getBitWidth(), V.isUnsigned())) { // sym cannot be any value greater than 'V'. This path is infeasible. @@ -155,56 +167,60 @@ const GRState *BasicConstraintManager::AssumeSymGT(const GRState *state, } // FIXME: For now have assuming x > y be the same as assuming sym != V; - return AssumeSymNE(state, sym, V); + return AssumeSymNE(state, sym, V, Adjustment); } -const GRState *BasicConstraintManager::AssumeSymGE(const GRState *state, - SymbolRef sym, - const llvm::APSInt &V) { - - // Reject a path if the value of sym is a constant X and !(X >= V). +const GRState* +BasicConstraintManager::AssumeSymGE(const GRState *state, SymbolRef sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) { + // Reject a path if the value of sym is a constant X and !(X+Adj >= V). if (const llvm::APSInt *X = getSymVal(state, sym)) { - bool isFeasible = *X >= V; + bool isFeasible = (*X >= V-Adjustment); return isFeasible ? state : NULL; } // Sym is not a constant, but it is worth looking to see if V is the // maximum integer value. if (V == llvm::APSInt::getMaxValue(V.getBitWidth(), V.isUnsigned())) { - // If we know that sym != V, then this condition is infeasible since - // there is no other value greater than V. - bool isFeasible = !isNotEqual(state, sym, V); + llvm::APSInt Adjusted = V-Adjustment; + + // If we know that sym != V (after adjustment), then this condition + // is infeasible since there is no other value greater than V. + bool isFeasible = !isNotEqual(state, sym, Adjusted); // If the path is still feasible then as a consequence we know that - // 'sym == V' because we cannot have 'sym > V' (no larger values). + // 'sym+Adjustment == V' because there are no larger values. // Add this constraint. - return isFeasible ? AddEQ(state, sym, V) : NULL; + return isFeasible ? AddEQ(state, sym, Adjusted) : NULL; } return state; } const GRState* -BasicConstraintManager::AssumeSymLE(const GRState* state, SymbolRef sym, - const llvm::APSInt& V) { - - // Reject a path if the value of sym is a constant X and !(X <= V). +BasicConstraintManager::AssumeSymLE(const GRState *state, SymbolRef sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) { + // Reject a path if the value of sym is a constant X and !(X+Adj <= V). if (const llvm::APSInt* X = getSymVal(state, sym)) { - bool isFeasible = *X <= V; + bool isFeasible = (*X <= V-Adjustment); return isFeasible ? state : NULL; } // Sym is not a constant, but it is worth looking to see if V is the // minimum integer value. if (V == llvm::APSInt::getMinValue(V.getBitWidth(), V.isUnsigned())) { - // If we know that sym != V, then this condition is infeasible since - // there is no other value less than V. - bool isFeasible = !isNotEqual(state, sym, V); + llvm::APSInt Adjusted = V-Adjustment; + + // If we know that sym != V (after adjustment), then this condition + // is infeasible since there is no other value less than V. + bool isFeasible = !isNotEqual(state, sym, Adjusted); // If the path is still feasible then as a consequence we know that - // 'sym == V' because we cannot have 'sym < V' (no smaller values). + // 'sym+Adjustment == V' because there are no smaller values. // Add this constraint. - return isFeasible ? AddEQ(state, sym, V) : NULL; + return isFeasible ? AddEQ(state, sym, Adjusted) : NULL; } return state; @@ -213,7 +229,7 @@ BasicConstraintManager::AssumeSymLE(const GRState* state, SymbolRef sym, const GRState* BasicConstraintManager::AddEQ(const GRState* state, SymbolRef sym, const llvm::APSInt& V) { // Create a new state with the old binding replaced. - return state->set<ConstEq>(sym, &V); + return state->set<ConstEq>(sym, &state->getBasicVals().getValue(V)); } const GRState* BasicConstraintManager::AddNE(const GRState* state, SymbolRef sym, @@ -224,7 +240,7 @@ const GRState* BasicConstraintManager::AddNE(const GRState* state, SymbolRef sym GRState::IntSetTy S = T ? *T : ISetFactory.GetEmptySet(); // Now add V to the NE set. - S = ISetFactory.Add(S, &V); + S = ISetFactory.Add(S, &state->getBasicVals().getValue(V)); // Create a new state with the old binding replaced. return state->set<ConstNotEq>(sym, S); @@ -243,7 +259,7 @@ bool BasicConstraintManager::isNotEqual(const GRState* state, SymbolRef sym, const ConstNotEqTy::data_type* T = state->get<ConstNotEq>(sym); // See if V is present in the NE-set. - return T ? T->contains(&V) : false; + return T ? T->contains(&state->getBasicVals().getValue(V)) : false; } bool BasicConstraintManager::isEqual(const GRState* state, SymbolRef sym, diff --git a/lib/Checker/BasicObjCFoundationChecks.cpp b/lib/Checker/BasicObjCFoundationChecks.cpp index b852e2ad9a48..ecb2d1c4e34b 100644 --- a/lib/Checker/BasicObjCFoundationChecks.cpp +++ b/lib/Checker/BasicObjCFoundationChecks.cpp @@ -415,59 +415,72 @@ clang::CreateAuditCFNumberCreate(ASTContext& Ctx, BugReporter& BR) { } //===----------------------------------------------------------------------===// -// CFRetain/CFRelease auditing for null arguments. +// CFRetain/CFRelease checking for null arguments. //===----------------------------------------------------------------------===// namespace { -class AuditCFRetainRelease : public GRSimpleAPICheck { +class CFRetainReleaseChecker : public CheckerVisitor<CFRetainReleaseChecker> { APIMisuse *BT; - - // FIXME: Either this should be refactored into GRSimpleAPICheck, or - // it should always be passed with a call to Audit. The latter - // approach makes this class more stateless. - ASTContext& Ctx; IdentifierInfo *Retain, *Release; - BugReporter& BR; public: - AuditCFRetainRelease(ASTContext& ctx, BugReporter& br) - : BT(0), Ctx(ctx), - Retain(&Ctx.Idents.get("CFRetain")), Release(&Ctx.Idents.get("CFRelease")), - BR(br){} + CFRetainReleaseChecker(ASTContext& Ctx): BT(NULL), + Retain(&Ctx.Idents.get("CFRetain")), Release(&Ctx.Idents.get("CFRelease")) + {} - ~AuditCFRetainRelease() {} + static void *getTag() { static int x = 0; return &x; } - bool Audit(ExplodedNode* N, GRStateManager&); + void PreVisitCallExpr(CheckerContext& C, const CallExpr* CE); }; } // end anonymous namespace -bool AuditCFRetainRelease::Audit(ExplodedNode* N, GRStateManager&) { - const CallExpr* CE = cast<CallExpr>(cast<PostStmt>(N->getLocation()).getStmt()); - +void CFRetainReleaseChecker::PreVisitCallExpr(CheckerContext& C, + const CallExpr* CE) { // If the CallExpr doesn't have exactly 1 argument just give up checking. if (CE->getNumArgs() != 1) - return false; + return; - // Check if we called CFRetain/CFRelease. - const GRState* state = N->getState(); + // Get the function declaration of the callee. + const GRState* state = C.getState(); SVal X = state->getSVal(CE->getCallee()); const FunctionDecl* FD = X.getAsFunctionDecl(); if (!FD) - return false; + return; + // Check if we called CFRetain/CFRelease. const IdentifierInfo *FuncII = FD->getIdentifier(); if (!(FuncII == Retain || FuncII == Release)) - return false; + return; + + // FIXME: The rest of this just checks that the argument is non-null. + // It should probably be refactored and combined with AttrNonNullChecker. + + // Get the argument's value. + const Expr *Arg = CE->getArg(0); + SVal ArgVal = state->getSVal(Arg); + DefinedSVal *DefArgVal = dyn_cast<DefinedSVal>(&ArgVal); + if (!DefArgVal) + return; + + // Get a NULL value. + ValueManager &ValMgr = C.getValueManager(); + DefinedSVal Zero = cast<DefinedSVal>(ValMgr.makeZeroVal(Arg->getType())); + + // Make an expression asserting that they're equal. + SValuator &SVator = ValMgr.getSValuator(); + DefinedOrUnknownSVal ArgIsNull = SVator.EvalEQ(state, Zero, *DefArgVal); + + // Are they equal? + const GRState *stateTrue, *stateFalse; + llvm::tie(stateTrue, stateFalse) = state->Assume(ArgIsNull); + + if (stateTrue && !stateFalse) { + ExplodedNode *N = C.GenerateSink(stateTrue); + if (!N) + return; - // Finally, check if the argument is NULL. - // FIXME: We should be able to bifurcate the state here, as a successful - // check will result in the value not being NULL afterwards. - // FIXME: Need a way to register vistors for the BugReporter. Would like - // to benefit from the same diagnostics that regular null dereference - // reporting has. - if (state->getStateManager().isEqual(state, CE->getArg(0), 0)) { if (!BT) BT = new APIMisuse("null passed to CFRetain/CFRelease"); @@ -475,19 +488,16 @@ bool AuditCFRetainRelease::Audit(ExplodedNode* N, GRStateManager&) { ? "Null pointer argument in call to CFRetain" : "Null pointer argument in call to CFRelease"; - RangedBugReport *report = new RangedBugReport(*BT, description, N); - report->addRange(CE->getArg(0)->getSourceRange()); - BR.EmitReport(report); - return true; - } - - return false; -} + EnhancedBugReport *report = new EnhancedBugReport(*BT, description, N); + report->addRange(Arg->getSourceRange()); + report->addVisitorCreator(bugreporter::registerTrackNullOrUndefValue, Arg); + C.EmitReport(report); + return; + } -GRSimpleAPICheck* -clang::CreateAuditCFRetainRelease(ASTContext& Ctx, BugReporter& BR) { - return new AuditCFRetainRelease(Ctx, BR); + // From here on, we know the argument is non-null. + C.addTransition(stateFalse); } //===----------------------------------------------------------------------===// @@ -569,9 +579,10 @@ void clang::RegisterAppleChecks(GRExprEngine& Eng, const Decl &D) { Eng.AddCheck(CreateBasicObjCFoundationChecks(Ctx, BR), Stmt::ObjCMessageExprClass); Eng.AddCheck(CreateAuditCFNumberCreate(Ctx, BR), Stmt::CallExprClass); - Eng.AddCheck(CreateAuditCFRetainRelease(Ctx, BR), Stmt::CallExprClass); RegisterNSErrorChecks(BR, Eng, D); RegisterNSAutoreleasePoolChecks(Eng); + + Eng.registerCheck(new CFRetainReleaseChecker(Ctx)); Eng.registerCheck(new ClassReleaseChecker(Ctx)); } diff --git a/lib/Checker/BasicObjCFoundationChecks.h b/lib/Checker/BasicObjCFoundationChecks.h index 679c6dc1df2d..8fb057087086 100644 --- a/lib/Checker/BasicObjCFoundationChecks.h +++ b/lib/Checker/BasicObjCFoundationChecks.h @@ -30,9 +30,6 @@ GRSimpleAPICheck *CreateBasicObjCFoundationChecks(ASTContext& Ctx, GRSimpleAPICheck *CreateAuditCFNumberCreate(ASTContext& Ctx, BugReporter& BR); -GRSimpleAPICheck *CreateAuditCFRetainRelease(ASTContext& Ctx, - BugReporter& BR); - void RegisterNSErrorChecks(BugReporter& BR, GRExprEngine &Eng, const Decl &D); void RegisterNSAutoreleasePoolChecks(GRExprEngine &Eng); diff --git a/lib/Checker/BasicStore.cpp b/lib/Checker/BasicStore.cpp index 5be5ca615ed6..62c8d9c248ae 100644 --- a/lib/Checker/BasicStore.cpp +++ b/lib/Checker/BasicStore.cpp @@ -46,9 +46,14 @@ public: SVal Retrieve(Store store, Loc loc, QualType T = QualType()); - Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E, + Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E, unsigned Count, InvalidatedSymbols *IS); + Store InvalidateRegions(Store store, const MemRegion * const *Begin, + const MemRegion * const *End, const Expr *E, + unsigned Count, InvalidatedSymbols *IS, + bool invalidateGlobals); + Store scanForIvars(Stmt *B, const Decl* SelfDecl, const MemRegion *SelfRegion, Store St); @@ -72,9 +77,9 @@ public: /// RemoveDeadBindings - Scans a BasicStore of 'state' for dead values. /// It updatees the GRState object in place with the values removed. - const GRState *RemoveDeadBindings(GRState &state, Stmt* Loc, - const StackFrameContext *LCtx, - SymbolReaper& SymReaper, + const GRState *RemoveDeadBindings(GRState &state, + const StackFrameContext *LCtx, + SymbolReaper& SymReaper, llvm::SmallVectorImpl<const MemRegion*>& RegionRoots); void iterBindings(Store store, BindingsHandler& f); @@ -144,9 +149,30 @@ SVal BasicStoreManager::LazyRetrieve(Store store, const TypedRegion *R) { // Globals and parameters start with symbolic values. // Local variables initially are undefined. + + // Non-static globals may have had their values reset by InvalidateRegions. + const MemSpaceRegion *MS = VR->getMemorySpace(); + if (isa<NonStaticGlobalSpaceRegion>(MS)) { + BindingsTy B = GetBindings(store); + // FIXME: Copy-and-pasted from RegionStore.cpp. + if (BindingsTy::data_type *Val = B.lookup(MS)) { + if (SymbolRef parentSym = Val->getAsSymbol()) + return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R); + + if (Val->isZeroConstant()) + return ValMgr.makeZeroVal(T); + + if (Val->isUnknownOrUndef()) + return *Val; + + assert(0 && "Unknown default value."); + } + } + if (VR->hasGlobalsOrParametersStorage() || isa<UnknownSpaceRegion>(VR->getMemorySpace())) return ValMgr.getRegionValueSymbolVal(R); + return UndefinedVal(); } @@ -194,6 +220,14 @@ Store BasicStoreManager::Bind(Store store, Loc loc, SVal V) { return store; const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion(); + + // Special case: a default symbol assigned to the NonStaticGlobalsSpaceRegion + // that is used to derive other symbols. + if (isa<NonStaticGlobalSpaceRegion>(R)) { + BindingsTy B = GetBindings(store); + return VBFactory.Add(B, R, V).getRoot(); + } + ASTContext &C = StateMgr.getContext(); // Special case: handle store of pointer values (Loc) to pointers via @@ -251,7 +285,7 @@ Store BasicStoreManager::Remove(Store store, Loc loc) { } } -const GRState *BasicStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc, +const GRState *BasicStoreManager::RemoveDeadBindings(GRState &state, const StackFrameContext *LCtx, SymbolReaper& SymReaper, llvm::SmallVectorImpl<const MemRegion*>& RegionRoots) @@ -263,14 +297,14 @@ const GRState *BasicStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc, // Iterate over the variable bindings. for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) { if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) { - if (SymReaper.isLive(Loc, VR)) + if (SymReaper.isLive(VR)) RegionRoots.push_back(VR); else continue; } - else if (isa<ObjCIvarRegion>(I.getKey())) { + else if (isa<ObjCIvarRegion>(I.getKey()) || + isa<NonStaticGlobalSpaceRegion>(I.getKey())) RegionRoots.push_back(I.getKey()); - } else continue; @@ -292,7 +326,8 @@ const GRState *BasicStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc, SymReaper.markLive(SymR->getSymbol()); break; } - else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR)) { + else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR) || + isa<NonStaticGlobalSpaceRegion>(MR)) { if (Marked.count(MR)) break; @@ -475,7 +510,8 @@ void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) { BindingsTy B = GetBindings(store); for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) - f.HandleBinding(*this, store, I.getKey(), I.getData()); + if (!f.HandleBinding(*this, store, I.getKey(), I.getData())) + return; } @@ -485,6 +521,49 @@ StoreManager::BindingsHandler::~BindingsHandler() {} // Binding invalidation. //===----------------------------------------------------------------------===// + +Store BasicStoreManager::InvalidateRegions(Store store, + const MemRegion * const *I, + const MemRegion * const *End, + const Expr *E, unsigned Count, + InvalidatedSymbols *IS, + bool invalidateGlobals) { + if (invalidateGlobals) { + BindingsTy B = GetBindings(store); + for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) { + const MemRegion *R = I.getKey(); + if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace())) + store = InvalidateRegion(store, R, E, Count, IS); + } + } + + for ( ; I != End ; ++I) { + const MemRegion *R = *I; + // Don't invalidate globals twice. + if (invalidateGlobals) { + if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace())) + continue; + } + store = InvalidateRegion(store, *I, E, Count, IS); + } + + // FIXME: This is copy-and-paste from RegionStore.cpp. + if (invalidateGlobals) { + // Bind the non-static globals memory space to a new symbol that we will + // use to derive the bindings for all non-static globals. + const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(); + SVal V = + ValMgr.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, E, + /* symbol type, doesn't matter */ Ctx.IntTy, + Count); + + store = Bind(store, loc::MemRegionVal(GS), V); + } + + return store; +} + + Store BasicStoreManager::InvalidateRegion(Store store, const MemRegion *R, const Expr *E, diff --git a/lib/Checker/BugReporter.cpp b/lib/Checker/BugReporter.cpp index 3bcc03f4f29c..0422d80ae26d 100644 --- a/lib/Checker/BugReporter.cpp +++ b/lib/Checker/BugReporter.cpp @@ -925,7 +925,7 @@ public: // statement (if it doesn't already exist). // FIXME: Should handle CXXTryStmt if analyser starts supporting C++. if (const CompoundStmt *CS = - PDB.getCodeDecl().getCompoundBody()) + dyn_cast_or_null<CompoundStmt>(PDB.getCodeDecl().getBody())) if (!CS->body_empty()) { SourceLocation Loc = (*CS->body_begin())->getLocStart(); rawAddEdge(PathDiagnosticLocation(Loc, PDB.getSourceManager())); @@ -1403,7 +1403,7 @@ MakeReportGraph(const ExplodedGraph* G, // Create a new (third!) graph with a single path. This is the graph // that will be returned to the caller. - ExplodedGraph *GNew = new ExplodedGraph(GTrim->getContext()); + ExplodedGraph *GNew = new ExplodedGraph(); // Sometimes the trimmed graph can contain a cycle. Perform a reverse BFS // to the root node, and then construct a new graph that contains only diff --git a/lib/Checker/BuiltinFunctionChecker.cpp b/lib/Checker/BuiltinFunctionChecker.cpp index 9c8b51657b26..057e474626f6 100644 --- a/lib/Checker/BuiltinFunctionChecker.cpp +++ b/lib/Checker/BuiltinFunctionChecker.cpp @@ -57,15 +57,24 @@ bool BuiltinFunctionChecker::EvalCallExpr(CheckerContext &C,const CallExpr *CE){ case Builtin::BI__builtin_alloca: { // FIXME: Refactor into StoreManager itself? MemRegionManager& RM = C.getStoreManager().getRegionManager(); - const MemRegion* R = + const AllocaRegion* R = RM.getAllocaRegion(CE, C.getNodeBuilder().getCurrentBlockCount(), C.getPredecessor()->getLocationContext()); // Set the extent of the region in bytes. This enables us to use the // SVal of the argument directly. If we save the extent in bits, we // cannot represent values like symbol*8. - SVal Extent = state->getSVal(*(CE->arg_begin())); - state = C.getStoreManager().setExtent(state, R, Extent); + DefinedOrUnknownSVal Size = + cast<DefinedOrUnknownSVal>(state->getSVal(*(CE->arg_begin()))); + + ValueManager& ValMgr = C.getValueManager(); + DefinedOrUnknownSVal Extent = R->getExtent(ValMgr); + + SValuator& SVator = ValMgr.getSValuator(); + DefinedOrUnknownSVal ExtentMatchesSizeArg = + SVator.EvalEQ(state, Extent, Size); + state = state->Assume(ExtentMatchesSizeArg, true); + C.GenerateNode(state->BindExpr(CE, loc::MemRegionVal(R))); return true; } diff --git a/lib/Checker/CFRefCount.cpp b/lib/Checker/CFRefCount.cpp index 42e6f67f0172..3c74cd8f9b27 100644 --- a/lib/Checker/CFRefCount.cpp +++ b/lib/Checker/CFRefCount.cpp @@ -228,111 +228,111 @@ public: ErrorOverAutorelease, ErrorReturnedNotOwned }; - + private: Kind kind; RetEffect::ObjKind okind; unsigned Cnt; unsigned ACnt; QualType T; - + RefVal(Kind k, RetEffect::ObjKind o, unsigned cnt, unsigned acnt, QualType t) : kind(k), okind(o), Cnt(cnt), ACnt(acnt), T(t) {} - + RefVal(Kind k, unsigned cnt = 0) : kind(k), okind(RetEffect::AnyObj), Cnt(cnt), ACnt(0) {} - + public: Kind getKind() const { return kind; } - + RetEffect::ObjKind getObjKind() const { return okind; } - + unsigned getCount() const { return Cnt; } unsigned getAutoreleaseCount() const { return ACnt; } unsigned getCombinedCounts() const { return Cnt + ACnt; } void clearCounts() { Cnt = 0; ACnt = 0; } void setCount(unsigned i) { Cnt = i; } void setAutoreleaseCount(unsigned i) { ACnt = i; } - + QualType getType() const { return T; } - + // Useful predicates. - + static bool isError(Kind k) { return k >= ERROR_START; } - + static bool isLeak(Kind k) { return k >= ERROR_LEAK_START; } - + bool isOwned() const { return getKind() == Owned; } - + bool isNotOwned() const { return getKind() == NotOwned; } - + bool isReturnedOwned() const { return getKind() == ReturnedOwned; } - + bool isReturnedNotOwned() const { return getKind() == ReturnedNotOwned; } - + bool isNonLeakError() const { Kind k = getKind(); return isError(k) && !isLeak(k); } - + static RefVal makeOwned(RetEffect::ObjKind o, QualType t, unsigned Count = 1) { return RefVal(Owned, o, Count, 0, t); } - + static RefVal makeNotOwned(RetEffect::ObjKind o, QualType t, unsigned Count = 0) { return RefVal(NotOwned, o, Count, 0, t); } - + // Comparison, profiling, and pretty-printing. - + bool operator==(const RefVal& X) const { return kind == X.kind && Cnt == X.Cnt && T == X.T && ACnt == X.ACnt; } - + RefVal operator-(size_t i) const { return RefVal(getKind(), getObjKind(), getCount() - i, getAutoreleaseCount(), getType()); } - + RefVal operator+(size_t i) const { return RefVal(getKind(), getObjKind(), getCount() + i, getAutoreleaseCount(), getType()); } - + RefVal operator^(Kind k) const { return RefVal(k, getObjKind(), getCount(), getAutoreleaseCount(), getType()); } - + RefVal autorelease() const { return RefVal(getKind(), getObjKind(), getCount(), getAutoreleaseCount()+1, getType()); } - + void Profile(llvm::FoldingSetNodeID& ID) const { ID.AddInteger((unsigned) kind); ID.AddInteger(Cnt); ID.AddInteger(ACnt); ID.Add(T); } - + void print(llvm::raw_ostream& Out) const; }; void RefVal::print(llvm::raw_ostream& Out) const { if (!T.isNull()) Out << "Tracked Type:" << T.getAsString() << '\n'; - + switch (getKind()) { default: assert(false); case Owned: { @@ -341,69 +341,69 @@ void RefVal::print(llvm::raw_ostream& Out) const { if (cnt) Out << " (+ " << cnt << ")"; break; } - + case NotOwned: { Out << "NotOwned"; unsigned cnt = getCount(); if (cnt) Out << " (+ " << cnt << ")"; break; } - + case ReturnedOwned: { Out << "ReturnedOwned"; unsigned cnt = getCount(); if (cnt) Out << " (+ " << cnt << ")"; break; } - + case ReturnedNotOwned: { Out << "ReturnedNotOwned"; unsigned cnt = getCount(); if (cnt) Out << " (+ " << cnt << ")"; break; } - + case Released: Out << "Released"; break; - + case ErrorDeallocGC: Out << "-dealloc (GC)"; break; - + case ErrorDeallocNotOwned: Out << "-dealloc (not-owned)"; break; - + case ErrorLeak: Out << "Leaked"; break; - + case ErrorLeakReturned: Out << "Leaked (Bad naming)"; break; - + case ErrorGCLeakReturned: Out << "Leaked (GC-ed at return)"; break; - + case ErrorUseAfterRelease: Out << "Use-After-Release [ERROR]"; break; - + case ErrorReleaseNotOwned: Out << "Release of Not-Owned [ERROR]"; break; - + case RefVal::ErrorOverAutorelease: Out << "Over autoreleased"; break; - + case RefVal::ErrorReturnedNotOwned: Out << "Non-owned object returned instead of owned"; break; } - + if (ACnt) { Out << " [ARC +" << ACnt << ']'; } @@ -897,7 +897,7 @@ public: RetainSummary *getInstanceMethodSummary(const ObjCMessageExpr *ME, const GRState *state, const LocationContext *LC); - + RetainSummary* getInstanceMethodSummary(const ObjCMessageExpr* ME, const ObjCInterfaceDecl* ID) { return getInstanceMethodSummary(ME->getSelector(), 0, @@ -927,7 +927,7 @@ public: break; } - return getClassMethodSummary(ME->getSelector(), + return getClassMethodSummary(ME->getSelector(), Class? Class->getIdentifier() : 0, Class, ME->getMethodDecl(), ME->getType()); @@ -1419,16 +1419,16 @@ RetainSummaryManager::getInstanceMethodSummary(const ObjCMessageExpr *ME, if (Receiver) { receiverV = state->getSValAsScalarOrLoc(Receiver); - + // FIXME: Eventually replace the use of state->get<RefBindings> with // a generic API for reasoning about the Objective-C types of symbolic // objects. if (SymbolRef Sym = receiverV.getAsLocSymbol()) if (const RefVal *T = state->get<RefBindings>(Sym)) - if (const ObjCObjectPointerType* PT = + if (const ObjCObjectPointerType* PT = T->getType()->getAs<ObjCObjectPointerType>()) ID = PT->getInterfaceDecl(); - + // FIXME: this is a hack. This may or may not be the actual method // that is called. if (!ID) { @@ -1444,7 +1444,7 @@ RetainSummaryManager::getInstanceMethodSummary(const ObjCMessageExpr *ME, // FIXME: The receiver could be a reference to a class, meaning that // we should use the class method. RetainSummary *Summ = getInstanceMethodSummary(ME, ID); - + // Special-case: are we sending a mesage to "self"? // This is a hack. When we have full-IP this should be removed. if (isa<ObjCMethodDecl>(LC->getDecl()) && Receiver) { @@ -1461,7 +1461,7 @@ RetainSummaryManager::getInstanceMethodSummary(const ObjCMessageExpr *ME, } } } - + return Summ ? Summ : getDefaultSummary(); } @@ -1849,7 +1849,7 @@ public: GRExprEngine& Engine, GRStmtNodeBuilder& Builder, ExplodedNode* Pred, - Stmt* S, const GRState* state, + const GRState* state, SymbolReaper& SymReaper); std::pair<ExplodedNode*, const GRState *> @@ -2619,7 +2619,7 @@ void CFRefCount::EvalSummary(ExplodedNodeSet& Dst, SymbolRef ErrorSym = 0; llvm::SmallVector<const MemRegion*, 10> RegionsToInvalidate; - + for (ExprIterator I = arg_beg; I != arg_end; ++I, ++idx) { SVal V = state->getSValAsScalarOrLoc(*I); SymbolRef Sym = V.getAsLocSymbol(); @@ -2659,7 +2659,7 @@ void CFRefCount::EvalSummary(ExplodedNodeSet& Dst, // approriately delegated to the respective StoreManagers while // still allowing us to do checker-specific logic (e.g., // invalidating reference counts), probably via callbacks. - if (ER->getElementType()->isIntegralType()) { + if (ER->getElementType()->isIntegralOrEnumerationType()) { const MemRegion *superReg = ER->getSuperRegion(); if (isa<VarRegion>(superReg) || isa<FieldRegion>(superReg) || isa<ObjCIvarRegion>(superReg)) @@ -2667,7 +2667,7 @@ void CFRefCount::EvalSummary(ExplodedNodeSet& Dst, } // FIXME: What about layers of ElementRegions? } - + // Mark this region for invalidation. We batch invalidate regions // below for efficiency. RegionsToInvalidate.push_back(R); @@ -2687,37 +2687,39 @@ void CFRefCount::EvalSummary(ExplodedNodeSet& Dst, goto tryAgain; } } - + // Block calls result in all captured values passed-via-reference to be // invalidated. if (const BlockDataRegion *BR = dyn_cast_or_null<BlockDataRegion>(Callee)) { RegionsToInvalidate.push_back(BR); } - + // Invalidate regions we designed for invalidation use the batch invalidation // API. - if (!RegionsToInvalidate.empty()) { - // FIXME: We can have collisions on the conjured symbol if the - // expression *I also creates conjured symbols. We probably want - // to identify conjured symbols by an expression pair: the enclosing - // expression (the context) and the expression itself. This should - // disambiguate conjured symbols. - unsigned Count = Builder.getCurrentBlockCount(); - StoreManager& StoreMgr = Eng.getStateManager().getStoreManager(); - - - StoreManager::InvalidatedSymbols IS; - Store store = state->getStore(); - store = StoreMgr.InvalidateRegions(store, RegionsToInvalidate.data(), - RegionsToInvalidate.data() + - RegionsToInvalidate.size(), - Ex, Count, &IS); - state = state->makeWithStore(store); - for (StoreManager::InvalidatedSymbols::iterator I = IS.begin(), - E = IS.end(); I!=E; ++I) { - // Remove any existing reference-count binding. - state = state->remove<RefBindings>(*I); - } + + // FIXME: We can have collisions on the conjured symbol if the + // expression *I also creates conjured symbols. We probably want + // to identify conjured symbols by an expression pair: the enclosing + // expression (the context) and the expression itself. This should + // disambiguate conjured symbols. + unsigned Count = Builder.getCurrentBlockCount(); + StoreManager& StoreMgr = Eng.getStateManager().getStoreManager(); + StoreManager::InvalidatedSymbols IS; + Store store = state->getStore(); + + // NOTE: Even if RegionsToInvalidate is empty, we must still invalidate + // global variables. + store = StoreMgr.InvalidateRegions(store, RegionsToInvalidate.data(), + RegionsToInvalidate.data() + + RegionsToInvalidate.size(), + Ex, Count, &IS, + /* invalidateGlobals = */ true); + + state = state->makeWithStore(store); + for (StoreManager::InvalidatedSymbols::iterator I = IS.begin(), + E = IS.end(); I!=E; ++I) { + // Remove any existing reference-count binding. + state = state->remove<RefBindings>(*I); } // Evaluate the effect on the message receiver. @@ -2862,7 +2864,7 @@ void CFRefCount::EvalCall(ExplodedNodeSet& Dst, ExplodedNode* Pred) { RetainSummary *Summ = 0; - + // FIXME: Better support for blocks. For now we stop tracking anything // that is passed to blocks. // FIXME: Need to handle variables that are "captured" by the block. @@ -3400,10 +3402,9 @@ void CFRefCount::EvalDeadSymbols(ExplodedNodeSet& Dst, GRExprEngine& Eng, GRStmtNodeBuilder& Builder, ExplodedNode* Pred, - Stmt* S, const GRState* state, SymbolReaper& SymReaper) { - + Stmt *S = Builder.getStmt(); RefBindings B = state->get<RefBindings>(); // Update counts from autorelease pools @@ -3501,7 +3502,7 @@ class RetainReleaseChecker public: RetainReleaseChecker(CFRefCount *tf) : TF(tf) {} static void* getTag() { static int x = 0; return &x; } - + void PostVisitBlockExpr(CheckerContext &C, const BlockExpr *BE); }; } // end anonymous namespace @@ -3509,29 +3510,29 @@ public: void RetainReleaseChecker::PostVisitBlockExpr(CheckerContext &C, const BlockExpr *BE) { - + // Scan the BlockDecRefExprs for any object the retain/release checker - // may be tracking. + // may be tracking. if (!BE->hasBlockDeclRefExprs()) return; - + const GRState *state = C.getState(); const BlockDataRegion *R = cast<BlockDataRegion>(state->getSVal(BE).getAsRegion()); - + BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(), E = R->referenced_vars_end(); - + if (I == E) return; - + // FIXME: For now we invalidate the tracking of all symbols passed to blocks // via captured variables, even though captured variables result in a copy // and in implicit increment/decrement of a retain count. llvm::SmallVector<const MemRegion*, 10> Regions; const LocationContext *LC = C.getPredecessor()->getLocationContext(); MemRegionManager &MemMgr = C.getValueManager().getRegionManager(); - + for ( ; I != E; ++I) { const VarRegion *VR = *I; if (VR->getSuperRegion() == R) { @@ -3539,7 +3540,7 @@ void RetainReleaseChecker::PostVisitBlockExpr(CheckerContext &C, } Regions.push_back(VR); } - + state = state->scanReachableSymbols<StopTrackingCallback>(Regions.data(), Regions.data() + Regions.size()).getState(); @@ -3552,28 +3553,28 @@ void RetainReleaseChecker::PostVisitBlockExpr(CheckerContext &C, void CFRefCount::RegisterChecks(GRExprEngine& Eng) { BugReporter &BR = Eng.getBugReporter(); - + useAfterRelease = new UseAfterRelease(this); BR.Register(useAfterRelease); - + releaseNotOwned = new BadRelease(this); BR.Register(releaseNotOwned); - + deallocGC = new DeallocGC(this); BR.Register(deallocGC); - + deallocNotOwned = new DeallocNotOwned(this); BR.Register(deallocNotOwned); - + overAutorelease = new OverAutorelease(this); BR.Register(overAutorelease); - + returnNotOwnedForOwned = new ReturnedNotOwnedForOwned(this); BR.Register(returnNotOwnedForOwned); - + // First register "return" leaks. const char* name = 0; - + if (isGCEnabled()) name = "Leak of returned object when using garbage collection"; else if (getLangOptions().getGCMode() == LangOptions::HybridGC) @@ -3583,12 +3584,12 @@ void CFRefCount::RegisterChecks(GRExprEngine& Eng) { assert(getLangOptions().getGCMode() == LangOptions::NonGC); name = "Leak of returned object"; } - + // Leaks should not be reported if they are post-dominated by a sink. leakAtReturn = new LeakAtReturn(this, name); leakAtReturn->setSuppressOnSink(true); BR.Register(leakAtReturn); - + // Second, register leaks within a function/method. if (isGCEnabled()) name = "Leak of object when using garbage collection"; @@ -3599,15 +3600,15 @@ void CFRefCount::RegisterChecks(GRExprEngine& Eng) { assert(getLangOptions().getGCMode() == LangOptions::NonGC); name = "Leak"; } - + // Leaks should not be reported if they are post-dominated by sinks. leakWithinFunction = new LeakWithinFunction(this, name); leakWithinFunction->setSuppressOnSink(true); BR.Register(leakWithinFunction); - + // Save the reference to the BugReporter. this->BR = &BR; - + // Register the RetainReleaseChecker with the GRExprEngine object. // Functionality in CFRefCount will be migrated to RetainReleaseChecker // over time. diff --git a/lib/Checker/CMakeLists.txt b/lib/Checker/CMakeLists.txt index 9c6adc6bf2ee..259346a97068 100644 --- a/lib/Checker/CMakeLists.txt +++ b/lib/Checker/CMakeLists.txt @@ -3,6 +3,7 @@ set(LLVM_NO_RTTI 1) add_clang_library(clangChecker AdjustedReturnValueChecker.cpp AggExprVisitor.cpp + AnalysisConsumer.cpp ArrayBoundChecker.cpp AttrNonNullChecker.cpp BasicConstraintManager.cpp @@ -12,63 +13,70 @@ add_clang_library(clangChecker BugReporter.cpp BugReporterVisitors.cpp BuiltinFunctionChecker.cpp + CFRefCount.cpp CallAndMessageChecker.cpp CallInliner.cpp CastSizeChecker.cpp CastToStructChecker.cpp - CFRefCount.cpp CheckDeadStores.cpp - Checker.cpp CheckObjCDealloc.cpp CheckObjCInstMethSignature.cpp CheckSecuritySyntaxOnly.cpp CheckSizeofPointer.cpp + Checker.cpp CocoaConventions.cpp + CStringChecker.cpp DereferenceChecker.cpp DivZeroChecker.cpp Environment.cpp ExplodedGraph.cpp FixedAddressChecker.cpp FlatStore.cpp + FrontendActions.cpp GRBlockCounter.cpp - GRCoreEngine.cpp GRCXXExprEngine.cpp + GRCoreEngine.cpp GRExprEngine.cpp GRExprEngineExperimentalChecks.cpp GRState.cpp + HTMLDiagnostics.cpp + IdempotentOperationChecker.cpp LLVMConventionsChecker.cpp MacOSXAPIChecker.cpp MallocChecker.cpp ManagerRegistry.cpp MemRegion.cpp - NoReturnFunctionChecker.cpp NSAutoreleasePoolChecker.cpp NSErrorChecker.cpp - ObjCUnusedIVarsChecker.cpp + NoReturnFunctionChecker.cpp OSAtomicChecker.cpp + ObjCUnusedIVarsChecker.cpp PathDiagnostic.cpp + PlistDiagnostics.cpp PointerArithChecker.cpp PointerSubChecker.cpp PthreadLockChecker.cpp RangeConstraintManager.cpp RegionStore.cpp ReturnPointerRangeChecker.cpp - ReturnStackAddressChecker.cpp ReturnUndefChecker.cpp + SVals.cpp + SValuator.cpp SimpleConstraintManager.cpp SimpleSValuator.cpp + StackAddrLeakChecker.cpp Store.cpp - SVals.cpp - SValuator.cpp + StreamChecker.cpp SymbolManager.cpp UndefBranchChecker.cpp UndefCapturedBlockVarChecker.cpp + UndefResultChecker.cpp UndefinedArraySubscriptChecker.cpp UndefinedAssignmentChecker.cpp - UndefResultChecker.cpp UnixAPIChecker.cpp - ValueManager.cpp VLASizeChecker.cpp + ValueManager.cpp ) -add_dependencies(clangChecker ClangStmtNodes) +add_dependencies(clangChecker ClangAttrClasses ClangAttrList ClangDeclNodes + ClangStmtNodes) diff --git a/lib/Checker/CStringChecker.cpp b/lib/Checker/CStringChecker.cpp new file mode 100644 index 000000000000..a92d409703a3 --- /dev/null +++ b/lib/Checker/CStringChecker.cpp @@ -0,0 +1,525 @@ +//= CStringChecker.h - Checks calls to C string functions ----------*- C++ -*-// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This defines CStringChecker, which is an assortment of checks on calls +// to functions in <string.h>. +// +//===----------------------------------------------------------------------===// + +#include "GRExprEngineExperimentalChecks.h" +#include "clang/Checker/BugReporter/BugType.h" +#include "clang/Checker/PathSensitive/CheckerVisitor.h" +#include "llvm/ADT/StringSwitch.h" + +using namespace clang; + +namespace { +class CStringChecker : public CheckerVisitor<CStringChecker> { + BugType *BT_Null, *BT_Bounds, *BT_Overlap; +public: + CStringChecker() + : BT_Null(0), BT_Bounds(0), BT_Overlap(0) {} + static void *getTag() { static int tag; return &tag; } + + bool EvalCallExpr(CheckerContext &C, const CallExpr *CE); + + typedef void (CStringChecker::*FnCheck)(CheckerContext &, const CallExpr *); + + void EvalMemcpy(CheckerContext &C, const CallExpr *CE); + void EvalMemmove(CheckerContext &C, const CallExpr *CE); + void EvalBcopy(CheckerContext &C, const CallExpr *CE); + void EvalCopyCommon(CheckerContext &C, const GRState *state, + const Expr *Size, const Expr *Source, const Expr *Dest, + bool Restricted = false); + + void EvalMemcmp(CheckerContext &C, const CallExpr *CE); + + // Utility methods + std::pair<const GRState*, const GRState*> + AssumeZero(CheckerContext &C, const GRState *state, SVal V, QualType Ty); + + const GRState *CheckNonNull(CheckerContext &C, const GRState *state, + const Expr *S, SVal l); + const GRState *CheckLocation(CheckerContext &C, const GRState *state, + const Expr *S, SVal l); + const GRState *CheckBufferAccess(CheckerContext &C, const GRState *state, + const Expr *Size, + const Expr *FirstBuf, + const Expr *SecondBuf = NULL); + const GRState *CheckOverlap(CheckerContext &C, const GRState *state, + const Expr *Size, const Expr *First, + const Expr *Second); + void EmitOverlapBug(CheckerContext &C, const GRState *state, + const Stmt *First, const Stmt *Second); +}; +} //end anonymous namespace + +void clang::RegisterCStringChecker(GRExprEngine &Eng) { + Eng.registerCheck(new CStringChecker()); +} + +//===----------------------------------------------------------------------===// +// Individual checks and utility methods. +//===----------------------------------------------------------------------===// + +std::pair<const GRState*, const GRState*> +CStringChecker::AssumeZero(CheckerContext &C, const GRState *state, SVal V, + QualType Ty) { + DefinedSVal *Val = dyn_cast<DefinedSVal>(&V); + if (!Val) + return std::pair<const GRState*, const GRState *>(state, state); + + ValueManager &ValMgr = C.getValueManager(); + SValuator &SV = ValMgr.getSValuator(); + + DefinedOrUnknownSVal Zero = ValMgr.makeZeroVal(Ty); + DefinedOrUnknownSVal ValIsZero = SV.EvalEQ(state, *Val, Zero); + + return state->Assume(ValIsZero); +} + +const GRState *CStringChecker::CheckNonNull(CheckerContext &C, + const GRState *state, + const Expr *S, SVal l) { + // If a previous check has failed, propagate the failure. + if (!state) + return NULL; + + const GRState *stateNull, *stateNonNull; + llvm::tie(stateNull, stateNonNull) = AssumeZero(C, state, l, S->getType()); + + if (stateNull && !stateNonNull) { + ExplodedNode *N = C.GenerateSink(stateNull); + if (!N) + return NULL; + + if (!BT_Null) + BT_Null = new BuiltinBug("API", + "Null pointer argument in call to byte string function"); + + // Generate a report for this bug. + BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Null); + EnhancedBugReport *report = new EnhancedBugReport(*BT, + BT->getDescription(), N); + + report->addRange(S->getSourceRange()); + report->addVisitorCreator(bugreporter::registerTrackNullOrUndefValue, S); + C.EmitReport(report); + return NULL; + } + + // From here on, assume that the value is non-null. + assert(stateNonNull); + return stateNonNull; +} + +// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor? +const GRState *CStringChecker::CheckLocation(CheckerContext &C, + const GRState *state, + const Expr *S, SVal l) { + // If a previous check has failed, propagate the failure. + if (!state) + return NULL; + + // Check for out of bound array element access. + const MemRegion *R = l.getAsRegion(); + if (!R) + return state; + + const ElementRegion *ER = dyn_cast<ElementRegion>(R); + if (!ER) + return state; + + assert(ER->getValueType(C.getASTContext()) == C.getASTContext().CharTy && + "CheckLocation should only be called with char* ElementRegions"); + + // Get the size of the array. + const SubRegion *Super = cast<SubRegion>(ER->getSuperRegion()); + ValueManager &ValMgr = C.getValueManager(); + SVal Extent = ValMgr.convertToArrayIndex(Super->getExtent(ValMgr)); + DefinedOrUnknownSVal Size = cast<DefinedOrUnknownSVal>(Extent); + + // Get the index of the accessed element. + DefinedOrUnknownSVal &Idx = cast<DefinedOrUnknownSVal>(ER->getIndex()); + + const GRState *StInBound = state->AssumeInBound(Idx, Size, true); + const GRState *StOutBound = state->AssumeInBound(Idx, Size, false); + if (StOutBound && !StInBound) { + ExplodedNode *N = C.GenerateSink(StOutBound); + if (!N) + return NULL; + + if (!BT_Bounds) + BT_Bounds = new BuiltinBug("Out-of-bound array access", + "Byte string function accesses out-of-bound array element " + "(buffer overflow)"); + + // FIXME: It would be nice to eventually make this diagnostic more clear, + // e.g., by referencing the original declaration or by saying *why* this + // reference is outside the range. + + // Generate a report for this bug. + BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Bounds); + RangedBugReport *report = new RangedBugReport(*BT, BT->getDescription(), N); + + report->addRange(S->getSourceRange()); + C.EmitReport(report); + return NULL; + } + + // Array bound check succeeded. From this point forward the array bound + // should always succeed. + return StInBound; +} + +const GRState *CStringChecker::CheckBufferAccess(CheckerContext &C, + const GRState *state, + const Expr *Size, + const Expr *FirstBuf, + const Expr *SecondBuf) { + // If a previous check has failed, propagate the failure. + if (!state) + return NULL; + + ValueManager &VM = C.getValueManager(); + SValuator &SV = VM.getSValuator(); + ASTContext &Ctx = C.getASTContext(); + + QualType SizeTy = Ctx.getSizeType(); + QualType PtrTy = Ctx.getPointerType(Ctx.CharTy); + + // Check that the first buffer is non-null. + SVal BufVal = state->getSVal(FirstBuf); + state = CheckNonNull(C, state, FirstBuf, BufVal); + if (!state) + return NULL; + + // Get the access length and make sure it is known. + SVal LengthVal = state->getSVal(Size); + NonLoc *Length = dyn_cast<NonLoc>(&LengthVal); + if (!Length) + return state; + + // Compute the offset of the last element to be accessed: size-1. + NonLoc One = cast<NonLoc>(VM.makeIntVal(1, SizeTy)); + NonLoc LastOffset = cast<NonLoc>(SV.EvalBinOpNN(state, BinaryOperator::Sub, + *Length, One, SizeTy)); + + // Check that the first buffer is sufficently long. + Loc BufStart = cast<Loc>(SV.EvalCast(BufVal, PtrTy, FirstBuf->getType())); + SVal BufEnd + = SV.EvalBinOpLN(state, BinaryOperator::Add, BufStart, LastOffset, PtrTy); + state = CheckLocation(C, state, FirstBuf, BufEnd); + + // If the buffer isn't large enough, abort. + if (!state) + return NULL; + + // If there's a second buffer, check it as well. + if (SecondBuf) { + BufVal = state->getSVal(SecondBuf); + state = CheckNonNull(C, state, SecondBuf, BufVal); + if (!state) + return NULL; + + BufStart = cast<Loc>(SV.EvalCast(BufVal, PtrTy, SecondBuf->getType())); + BufEnd + = SV.EvalBinOpLN(state, BinaryOperator::Add, BufStart, LastOffset, PtrTy); + state = CheckLocation(C, state, SecondBuf, BufEnd); + } + + // Large enough or not, return this state! + return state; +} + +const GRState *CStringChecker::CheckOverlap(CheckerContext &C, + const GRState *state, + const Expr *Size, + const Expr *First, + const Expr *Second) { + // Do a simple check for overlap: if the two arguments are from the same + // buffer, see if the end of the first is greater than the start of the second + // or vice versa. + + // If a previous check has failed, propagate the failure. + if (!state) + return NULL; + + ValueManager &VM = state->getStateManager().getValueManager(); + SValuator &SV = VM.getSValuator(); + ASTContext &Ctx = VM.getContext(); + const GRState *stateTrue, *stateFalse; + + // Get the buffer values and make sure they're known locations. + SVal FirstVal = state->getSVal(First); + SVal SecondVal = state->getSVal(Second); + + Loc *FirstLoc = dyn_cast<Loc>(&FirstVal); + if (!FirstLoc) + return state; + + Loc *SecondLoc = dyn_cast<Loc>(&SecondVal); + if (!SecondLoc) + return state; + + // Are the two values the same? + DefinedOrUnknownSVal EqualTest = SV.EvalEQ(state, *FirstLoc, *SecondLoc); + llvm::tie(stateTrue, stateFalse) = state->Assume(EqualTest); + + if (stateTrue && !stateFalse) { + // If the values are known to be equal, that's automatically an overlap. + EmitOverlapBug(C, stateTrue, First, Second); + return NULL; + } + + // Assume the two expressions are not equal. + assert(stateFalse); + state = stateFalse; + + // Which value comes first? + QualType CmpTy = Ctx.IntTy; + SVal Reverse = SV.EvalBinOpLL(state, BinaryOperator::GT, + *FirstLoc, *SecondLoc, CmpTy); + DefinedOrUnknownSVal *ReverseTest = dyn_cast<DefinedOrUnknownSVal>(&Reverse); + if (!ReverseTest) + return state; + + llvm::tie(stateTrue, stateFalse) = state->Assume(*ReverseTest); + + if (stateTrue) { + if (stateFalse) { + // If we don't know which one comes first, we can't perform this test. + return state; + } else { + // Switch the values so that FirstVal is before SecondVal. + Loc *tmpLoc = FirstLoc; + FirstLoc = SecondLoc; + SecondLoc = tmpLoc; + + // Switch the Exprs as well, so that they still correspond. + const Expr *tmpExpr = First; + First = Second; + Second = tmpExpr; + } + } + + // Get the length, and make sure it too is known. + SVal LengthVal = state->getSVal(Size); + NonLoc *Length = dyn_cast<NonLoc>(&LengthVal); + if (!Length) + return state; + + // Convert the first buffer's start address to char*. + // Bail out if the cast fails. + QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy); + SVal FirstStart = SV.EvalCast(*FirstLoc, CharPtrTy, First->getType()); + Loc *FirstStartLoc = dyn_cast<Loc>(&FirstStart); + if (!FirstStartLoc) + return state; + + // Compute the end of the first buffer. Bail out if THAT fails. + SVal FirstEnd = SV.EvalBinOpLN(state, BinaryOperator::Add, + *FirstStartLoc, *Length, CharPtrTy); + Loc *FirstEndLoc = dyn_cast<Loc>(&FirstEnd); + if (!FirstEndLoc) + return state; + + // Is the end of the first buffer past the start of the second buffer? + SVal Overlap = SV.EvalBinOpLL(state, BinaryOperator::GT, + *FirstEndLoc, *SecondLoc, CmpTy); + DefinedOrUnknownSVal *OverlapTest = dyn_cast<DefinedOrUnknownSVal>(&Overlap); + if (!OverlapTest) + return state; + + llvm::tie(stateTrue, stateFalse) = state->Assume(*OverlapTest); + + if (stateTrue && !stateFalse) { + // Overlap! + EmitOverlapBug(C, stateTrue, First, Second); + return NULL; + } + + // Assume the two expressions don't overlap. + assert(stateFalse); + return stateFalse; +} + +void CStringChecker::EmitOverlapBug(CheckerContext &C, const GRState *state, + const Stmt *First, const Stmt *Second) { + ExplodedNode *N = C.GenerateSink(state); + if (!N) + return; + + if (!BT_Overlap) + BT_Overlap = new BugType("Unix API", "Improper arguments"); + + // Generate a report for this bug. + RangedBugReport *report = + new RangedBugReport(*BT_Overlap, + "Arguments must not be overlapping buffers", N); + report->addRange(First->getSourceRange()); + report->addRange(Second->getSourceRange()); + + C.EmitReport(report); +} + +//===----------------------------------------------------------------------===// +// Evaluation of individual function calls. +//===----------------------------------------------------------------------===// + +void CStringChecker::EvalCopyCommon(CheckerContext &C, const GRState *state, + const Expr *Size, const Expr *Dest, + const Expr *Source, bool Restricted) { + // See if the size argument is zero. + SVal SizeVal = state->getSVal(Size); + QualType SizeTy = Size->getType(); + + const GRState *StZeroSize, *StNonZeroSize; + llvm::tie(StZeroSize, StNonZeroSize) = AssumeZero(C, state, SizeVal, SizeTy); + + // If the size is zero, there won't be any actual memory access. + if (StZeroSize) + C.addTransition(StZeroSize); + + // If the size can be nonzero, we have to check the other arguments. + if (StNonZeroSize) { + state = StNonZeroSize; + state = CheckBufferAccess(C, state, Size, Dest, Source); + if (Restricted) + state = CheckOverlap(C, state, Size, Dest, Source); + if (state) + C.addTransition(state); + } +} + + +void CStringChecker::EvalMemcpy(CheckerContext &C, const CallExpr *CE) { + // void *memcpy(void *restrict dst, const void *restrict src, size_t n); + // The return value is the address of the destination buffer. + const Expr *Dest = CE->getArg(0); + const GRState *state = C.getState(); + state = state->BindExpr(CE, state->getSVal(Dest)); + EvalCopyCommon(C, state, CE->getArg(2), Dest, CE->getArg(1), true); +} + +void CStringChecker::EvalMemmove(CheckerContext &C, const CallExpr *CE) { + // void *memmove(void *dst, const void *src, size_t n); + // The return value is the address of the destination buffer. + const Expr *Dest = CE->getArg(0); + const GRState *state = C.getState(); + state = state->BindExpr(CE, state->getSVal(Dest)); + EvalCopyCommon(C, state, CE->getArg(2), Dest, CE->getArg(1)); +} + +void CStringChecker::EvalBcopy(CheckerContext &C, const CallExpr *CE) { + // void bcopy(const void *src, void *dst, size_t n); + EvalCopyCommon(C, C.getState(), CE->getArg(2), CE->getArg(1), CE->getArg(0)); +} + +void CStringChecker::EvalMemcmp(CheckerContext &C, const CallExpr *CE) { + // int memcmp(const void *s1, const void *s2, size_t n); + const Expr *Left = CE->getArg(0); + const Expr *Right = CE->getArg(1); + const Expr *Size = CE->getArg(2); + + const GRState *state = C.getState(); + ValueManager &ValMgr = C.getValueManager(); + SValuator &SV = ValMgr.getSValuator(); + + // See if the size argument is zero. + SVal SizeVal = state->getSVal(Size); + QualType SizeTy = Size->getType(); + + const GRState *StZeroSize, *StNonZeroSize; + llvm::tie(StZeroSize, StNonZeroSize) = AssumeZero(C, state, SizeVal, SizeTy); + + // If the size can be zero, the result will be 0 in that case, and we don't + // have to check either of the buffers. + if (StZeroSize) { + state = StZeroSize; + state = state->BindExpr(CE, ValMgr.makeZeroVal(CE->getType())); + C.addTransition(state); + } + + // If the size can be nonzero, we have to check the other arguments. + if (StNonZeroSize) { + state = StNonZeroSize; + + // If we know the two buffers are the same, we know the result is 0. + // First, get the two buffers' addresses. Another checker will have already + // made sure they're not undefined. + DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(state->getSVal(Left)); + DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(state->getSVal(Right)); + + // See if they are the same. + DefinedOrUnknownSVal SameBuf = SV.EvalEQ(state, LV, RV); + const GRState *StSameBuf, *StNotSameBuf; + llvm::tie(StSameBuf, StNotSameBuf) = state->Assume(SameBuf); + + // If the two arguments might be the same buffer, we know the result is zero, + // and we only need to check one size. + if (StSameBuf) { + state = StSameBuf; + state = CheckBufferAccess(C, state, Size, Left); + if (state) { + state = StSameBuf->BindExpr(CE, ValMgr.makeZeroVal(CE->getType())); + C.addTransition(state); + } + } + + // If the two arguments might be different buffers, we have to check the + // size of both of them. + if (StNotSameBuf) { + state = StNotSameBuf; + state = CheckBufferAccess(C, state, Size, Left, Right); + if (state) { + // The return value is the comparison result, which we don't know. + unsigned Count = C.getNodeBuilder().getCurrentBlockCount(); + SVal CmpV = ValMgr.getConjuredSymbolVal(NULL, CE, CE->getType(), Count); + state = state->BindExpr(CE, CmpV); + C.addTransition(state); + } + } + } +} + +//===----------------------------------------------------------------------===// +// The driver method. +//===----------------------------------------------------------------------===// + +bool CStringChecker::EvalCallExpr(CheckerContext &C, const CallExpr *CE) { + // Get the callee. All the functions we care about are C functions + // with simple identifiers. + const GRState *state = C.getState(); + const Expr *Callee = CE->getCallee(); + const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl(); + + if (!FD) + return false; + + // Get the name of the callee. If it's a builtin, strip off the prefix. + llvm::StringRef Name = FD->getName(); + if (Name.startswith("__builtin_")) + Name = Name.substr(10); + + FnCheck EvalFunction = llvm::StringSwitch<FnCheck>(Name) + .Cases("memcpy", "__memcpy_chk", &CStringChecker::EvalMemcpy) + .Cases("memcmp", "bcmp", &CStringChecker::EvalMemcmp) + .Cases("memmove", "__memmove_chk", &CStringChecker::EvalMemmove) + .Case("bcopy", &CStringChecker::EvalBcopy) + .Default(NULL); + + // If the callee isn't a string function, let another checker handle it. + if (!EvalFunction) + return false; + + // Check and evaluate the call. + (this->*EvalFunction)(C, CE); + return true; +} diff --git a/lib/Checker/CallInliner.cpp b/lib/Checker/CallInliner.cpp index 88e1a05d1191..c47e06c78fb2 100644 --- a/lib/Checker/CallInliner.cpp +++ b/lib/Checker/CallInliner.cpp @@ -42,7 +42,7 @@ bool CallInliner::EvalCallExpr(CheckerContext &C, const CallExpr *CE) { if (!FD) return false; - if (!FD->getBody(FD)) + if (!FD->hasBody(FD)) return false; // Now we have the definition of the callee, create a CallEnter node. diff --git a/lib/Checker/CastSizeChecker.cpp b/lib/Checker/CastSizeChecker.cpp index 754d775a65d1..a502c10cac16 100644 --- a/lib/Checker/CastSizeChecker.cpp +++ b/lib/Checker/CastSizeChecker.cpp @@ -44,7 +44,8 @@ void CastSizeChecker::PreVisitCastExpr(CheckerContext &C, const CastExpr *CE) { QualType ToPointeeTy = ToPTy->getPointeeType(); - const MemRegion *R = C.getState()->getSVal(E).getAsRegion(); + const GRState *state = C.getState(); + const MemRegion *R = state->getSVal(E).getAsRegion(); if (R == 0) return; @@ -52,17 +53,21 @@ void CastSizeChecker::PreVisitCastExpr(CheckerContext &C, const CastExpr *CE) { if (SR == 0) return; - llvm::Optional<SVal> V = - C.getEngine().getStoreManager().getExtent(C.getState(), SR); - if (!V) - return; + ValueManager &ValMgr = C.getValueManager(); + SVal Extent = SR->getExtent(ValMgr); - const nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(V); - if (!CI) + SValuator &SVator = ValMgr.getSValuator(); + const llvm::APSInt *ExtentInt = SVator.getKnownValue(state, Extent); + if (!ExtentInt) return; - CharUnits RegionSize = CharUnits::fromQuantity(CI->getValue().getSExtValue()); + CharUnits RegionSize = CharUnits::fromQuantity(ExtentInt->getSExtValue()); CharUnits TypeSize = C.getASTContext().getTypeSizeInChars(ToPointeeTy); + + // Ignore void, and a few other un-sizeable types. + if (TypeSize.isZero()) + return; + if (RegionSize % TypeSize != 0) { if (ExplodedNode *N = C.GenerateSink()) { if (!BT) diff --git a/lib/Checker/CheckSecuritySyntaxOnly.cpp b/lib/Checker/CheckSecuritySyntaxOnly.cpp index 74e12b18a81a..af85c2faee3a 100644 --- a/lib/Checker/CheckSecuritySyntaxOnly.cpp +++ b/lib/Checker/CheckSecuritySyntaxOnly.cpp @@ -191,8 +191,8 @@ void WalkAST::CheckLoopConditionForFloat(const ForStmt *FS) { const DeclRefExpr *drRHS = dyn_cast<DeclRefExpr>(B->getRHS()->IgnoreParens()); // Does at least one of the variables have a floating point type? - drLHS = drLHS && drLHS->getType()->isFloatingType() ? drLHS : NULL; - drRHS = drRHS && drRHS->getType()->isFloatingType() ? drRHS : NULL; + drLHS = drLHS && drLHS->getType()->isRealFloatingType() ? drLHS : NULL; + drRHS = drRHS && drRHS->getType()->isRealFloatingType() ? drRHS : NULL; if (!drLHS && !drRHS) return; diff --git a/lib/Checker/Environment.cpp b/lib/Checker/Environment.cpp index addfc21c1805..48152ceb46f0 100644 --- a/lib/Checker/Environment.cpp +++ b/lib/Checker/Environment.cpp @@ -125,7 +125,7 @@ static bool isBlockExprInCallers(const Stmt *E, const LocationContext *LC) { // - Mark the region in DRoots if the binding is a loc::MemRegionVal. Environment -EnvironmentManager::RemoveDeadBindings(Environment Env, const Stmt *S, +EnvironmentManager::RemoveDeadBindings(Environment Env, SymbolReaper &SymReaper, const GRState *ST, llvm::SmallVectorImpl<const MemRegion*> &DRoots) { @@ -163,7 +163,7 @@ EnvironmentManager::RemoveDeadBindings(Environment Env, const Stmt *S, if (!C.isBlkExpr(BlkExpr)) continue; - if (SymReaper.isLive(S, BlkExpr)) { + if (SymReaper.isLive(BlkExpr)) { // Copy the binding to the new map. NewEnv.ExprBindings = F.Add(NewEnv.ExprBindings, BlkExpr, X); diff --git a/lib/Checker/FlatStore.cpp b/lib/Checker/FlatStore.cpp index 7f1c579c6edb..64575b3c9783 100644 --- a/lib/Checker/FlatStore.cpp +++ b/lib/Checker/FlatStore.cpp @@ -44,7 +44,7 @@ public: } SVal ArrayToPointer(Loc Array); - const GRState *RemoveDeadBindings(GRState &state, Stmt* Loc, + const GRState *RemoveDeadBindings(GRState &state, const StackFrameContext *LCtx, SymbolReaper& SymReaper, llvm::SmallVectorImpl<const MemRegion*>& RegionRoots){ @@ -59,6 +59,11 @@ public: Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E, unsigned Count, InvalidatedSymbols *IS); + + Store InvalidateRegions(Store store, const MemRegion * const *I, + const MemRegion * const *E, const Expr *Ex, + unsigned Count, InvalidatedSymbols *IS, + bool invalidateGlobals); void print(Store store, llvm::raw_ostream& Out, const char* nl, const char *sep); @@ -141,9 +146,20 @@ Store FlatStoreManager::BindDeclWithNoInit(Store store, const VarRegion *VR) { return store; } +Store FlatStoreManager::InvalidateRegions(Store store, + const MemRegion * const *I, + const MemRegion * const *E, + const Expr *Ex, unsigned Count, + InvalidatedSymbols *IS, + bool invalidateGlobals) { + assert(false && "Not implemented"); + return store; +} + Store FlatStoreManager::InvalidateRegion(Store store, const MemRegion *R, const Expr *E, unsigned Count, InvalidatedSymbols *IS) { + assert(false && "Not implemented"); return store; } diff --git a/lib/Checker/FrontendActions.cpp b/lib/Checker/FrontendActions.cpp new file mode 100644 index 000000000000..d9a54a021bc9 --- /dev/null +++ b/lib/Checker/FrontendActions.cpp @@ -0,0 +1,21 @@ +//===--- FrontendActions.cpp ----------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "clang/Checker/FrontendActions.h" +#include "clang/Frontend/CompilerInstance.h" +#include "clang/Checker/AnalysisConsumer.h" +using namespace clang; + +ASTConsumer *AnalysisAction::CreateASTConsumer(CompilerInstance &CI, + llvm::StringRef InFile) { + return CreateAnalysisConsumer(CI.getPreprocessor(), + CI.getFrontendOpts().OutputFile, + CI.getAnalyzerOpts()); +} + diff --git a/lib/Checker/GRCoreEngine.cpp b/lib/Checker/GRCoreEngine.cpp index 23a87d303b4d..a816186a307d 100644 --- a/lib/Checker/GRCoreEngine.cpp +++ b/lib/Checker/GRCoreEngine.cpp @@ -221,6 +221,7 @@ bool GRCoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps) { } } + SubEngine.ProcessEndWorklist(WList->hasWork() || BlockAborted); return WList->hasWork(); } @@ -257,7 +258,10 @@ void GRCoreEngine::HandleBlockEdge(const BlockEdge& L, ExplodedNode* Pred) { // FIXME: Should we allow ProcessBlockEntrance to also manipulate state? if (ProcessBlockEntrance(Blk, Pred, WList->getBlockCounter())) - GenerateNode(BlockEntrance(Blk, Pred->getLocationContext()), Pred->State, Pred); + GenerateNode(BlockEntrance(Blk, Pred->getLocationContext()), + Pred->State, Pred); + else + BlockAborted = true; } void GRCoreEngine::HandleBlockEntrance(const BlockEntrance& L, diff --git a/lib/Checker/GRExprEngine.cpp b/lib/Checker/GRExprEngine.cpp index 24176586728c..4652a4c89ff3 100644 --- a/lib/Checker/GRExprEngine.cpp +++ b/lib/Checker/GRExprEngine.cpp @@ -172,15 +172,39 @@ public: void GRExprEngine::CheckerVisit(Stmt *S, ExplodedNodeSet &Dst, ExplodedNodeSet &Src, bool isPrevisit) { - if (Checkers.empty()) { + // Determine if we already have a cached 'CheckersOrdered' vector + // specifically tailored for the provided <Stmt kind, isPrevisit>. This + // can reduce the number of checkers actually called. + CheckersOrdered *CO = &Checkers; + llvm::OwningPtr<CheckersOrdered> NewCO; + + const std::pair<unsigned, unsigned> &K = + std::make_pair((unsigned)S->getStmtClass(), isPrevisit ? 1U : 0U); + + CheckersOrdered *& CO_Ref = COCache[K]; + + if (!CO_Ref) { + // If we have no previously cached CheckersOrdered vector for this + // statement kind, then create one. + NewCO.reset(new CheckersOrdered); + } + else { + // Use the already cached set. + CO = CO_Ref; + } + + if (CO->empty()) { + // If there are no checkers, return early without doing any + // more work. Dst.insert(Src); return; } ExplodedNodeSet Tmp; ExplodedNodeSet *PrevSet = &Src; + unsigned checkersEvaluated = 0; - for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E;++I){ + for (CheckersOrdered::iterator I=CO->begin(), E=CO->end(); I!=E; ++I){ ExplodedNodeSet *CurrSet = 0; if (I+1 == E) CurrSet = &Dst; @@ -190,12 +214,30 @@ void GRExprEngine::CheckerVisit(Stmt *S, ExplodedNodeSet &Dst, } void *tag = I->first; Checker *checker = I->second; + bool respondsToCallback = true; for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end(); - NI != NE; ++NI) - checker->GR_Visit(*CurrSet, *Builder, *this, S, *NI, tag, isPrevisit); + NI != NE; ++NI) { + + checker->GR_Visit(*CurrSet, *Builder, *this, S, *NI, tag, isPrevisit, + respondsToCallback); + + } + PrevSet = CurrSet; + + if (NewCO.get()) { + ++checkersEvaluated; + if (respondsToCallback) + NewCO->push_back(*I); + } } + + // If we built NewCO, check if we called all the checkers. This is important + // so that we know that we accurately determined the entire set of checkers + // that responds to this callback. + if (NewCO.get() && checkersEvaluated == Checkers.size()) + CO_Ref = NewCO.take(); // Don't autotransition. The CheckerContext objects should do this // automatically. @@ -312,18 +354,20 @@ static void RegisterInternalChecks(GRExprEngine &Eng) { // automatically. Note that the check itself is owned by the GRExprEngine // object. RegisterAdjustedReturnValueChecker(Eng); - RegisterAttrNonNullChecker(Eng); + // CallAndMessageChecker should be registered before AttrNonNullChecker, + // where we assume arguments are not undefined. RegisterCallAndMessageChecker(Eng); + RegisterAttrNonNullChecker(Eng); RegisterDereferenceChecker(Eng); RegisterVLASizeChecker(Eng); RegisterDivZeroChecker(Eng); - RegisterReturnStackAddressChecker(Eng); RegisterReturnUndefChecker(Eng); RegisterUndefinedArraySubscriptChecker(Eng); RegisterUndefinedAssignmentChecker(Eng); RegisterUndefBranchChecker(Eng); RegisterUndefCapturedBlockVarChecker(Eng); RegisterUndefResultChecker(Eng); + RegisterStackAddrLeakChecker(Eng); // This is not a checker yet. RegisterNoReturnFunctionChecker(Eng); @@ -335,10 +379,10 @@ static void RegisterInternalChecks(GRExprEngine &Eng) { GRExprEngine::GRExprEngine(AnalysisManager &mgr, GRTransferFuncs *tf) : AMgr(mgr), - CoreEngine(mgr.getASTContext(), *this), + CoreEngine(*this), G(CoreEngine.getGraph()), Builder(NULL), - StateMgr(G.getContext(), mgr.getStoreManagerCreator(), + StateMgr(getContext(), mgr.getStoreManagerCreator(), mgr.getConstraintManagerCreator(), G.getAllocator(), *this), SymMgr(StateMgr.getSymbolManager()), @@ -346,7 +390,7 @@ GRExprEngine::GRExprEngine(AnalysisManager &mgr, GRTransferFuncs *tf) SVator(ValMgr.getSValuator()), CurrentStmt(NULL), NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL), - RaiseSel(GetNullarySelector("raise", G.getContext())), + RaiseSel(GetNullarySelector("raise", getContext())), BR(mgr, *this), TF(tf) { // Register internal checks. RegisterInternalChecks(*this); @@ -359,8 +403,14 @@ GRExprEngine::GRExprEngine(AnalysisManager &mgr, GRTransferFuncs *tf) GRExprEngine::~GRExprEngine() { BR.FlushReports(); delete [] NSExceptionInstanceRaiseSelectors; + + // Delete the set of checkers. for (CheckersOrdered::iterator I=Checkers.begin(), E=Checkers.end(); I!=E;++I) delete I->second; + + for (CheckersOrderedCache::iterator I=COCache.begin(), E=COCache.end(); + I!=E;++I) + delete I->second; } //===----------------------------------------------------------------------===// @@ -464,6 +514,13 @@ const GRState *GRExprEngine::ProcessAssume(const GRState *state, SVal cond, return TF->EvalAssume(state, cond, assumption); } +void GRExprEngine::ProcessEndWorklist(bool hasWorkRemaining) { + for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end(); + I != E; ++I) { + I->second->VisitEndAnalysis(G, BR, hasWorkRemaining); + } +} + void GRExprEngine::ProcessStmt(CFGElement CE, GRStmtNodeBuilder& builder) { CurrentStmt = CE.getStmt(); PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), @@ -480,10 +537,10 @@ void GRExprEngine::ProcessStmt(CFGElement CE, GRStmtNodeBuilder& builder) { // Create the cleaned state. const ExplodedNode *BasePred = Builder->getBasePredecessor(); - SymbolReaper SymReaper(BasePred->getLocationContext(), SymMgr); + SymbolReaper SymReaper(BasePred->getLocationContext(), CurrentStmt, SymMgr); CleanedState = AMgr.shouldPurgeDead() - ? StateMgr.RemoveDeadBindings(EntryNode->getState(), CurrentStmt, + ? StateMgr.RemoveDeadBindings(EntryNode->getState(), BasePred->getLocationContext()->getCurrentStackFrame(), SymReaper) : EntryNode->getState(); @@ -502,7 +559,7 @@ void GRExprEngine::ProcessStmt(CFGElement CE, GRStmtNodeBuilder& builder) { // FIXME: This should soon be removed. ExplodedNodeSet Tmp2; - getTF().EvalDeadSymbols(Tmp2, *this, *Builder, EntryNode, CurrentStmt, + getTF().EvalDeadSymbols(Tmp2, *this, *Builder, EntryNode, CleanedState, SymReaper); if (Checkers.empty()) @@ -598,7 +655,7 @@ void GRExprEngine::Visit(Stmt* S, ExplodedNode* Pred, ExplodedNodeSet& Dst) { case Stmt::CXXTryStmtClass: case Stmt::CXXTypeidExprClass: case Stmt::CXXUnresolvedConstructExprClass: - case Stmt::CXXZeroInitValueExprClass: + case Stmt::CXXScalarValueInitExprClass: case Stmt::DependentScopeDeclRefExprClass: case Stmt::UnaryTypeTraitExprClass: case Stmt::UnresolvedLookupExprClass: @@ -627,10 +684,14 @@ void GRExprEngine::Visit(Stmt* S, ExplodedNode* Pred, ExplodedNodeSet& Dst) { llvm_unreachable("Stmt should not be in analyzer evaluation loop"); break; + case Stmt::GNUNullExprClass: { + MakeNode(Dst, S, Pred, GetState(Pred)->BindExpr(S, ValMgr.makeNull())); + break; + } + // Cases not handled yet; but will handle some day. case Stmt::DesignatedInitExprClass: case Stmt::ExtVectorElementExprClass: - case Stmt::GNUNullExprClass: case Stmt::ImaginaryLiteralClass: case Stmt::ImplicitValueInitExprClass: case Stmt::ObjCAtCatchStmtClass: @@ -901,7 +962,7 @@ void GRExprEngine::VisitLValue(Expr* Ex, ExplodedNode* Pred, // C++ stuff we don't support yet. case Stmt::CXXExprWithTemporariesClass: case Stmt::CXXMemberCallExprClass: - case Stmt::CXXZeroInitValueExprClass: { + case Stmt::CXXScalarValueInitExprClass: { SaveAndRestore<bool> OldSink(Builder->BuildSinks); Builder->BuildSinks = true; MakeNode(Dst, Ex, Pred, GetState(Pred)); @@ -998,16 +1059,21 @@ void GRExprEngine::VisitLValue(Expr* Ex, ExplodedNode* Pred, CreateCXXTemporaryObject(Ex, Pred, Dst); return; - default: + default: { // Arbitrary subexpressions can return aggregate temporaries that // can be used in a lvalue context. We need to enhance our support // of such temporaries in both the environment and the store, so right // now we just do a regular visit. - assert ((Ex->getType()->isAggregateType()) && - "Other kinds of expressions with non-aggregate/union types do" - " not have lvalues."); + + // NOTE: Do not use 'isAggregateType()' here as CXXRecordDecls that + // are non-pod are not aggregates. + assert ((isa<RecordType>(Ex->getType().getDesugaredType()) || + isa<ArrayType>(Ex->getType().getDesugaredType())) && + "Other kinds of expressions with non-aggregate/union/class types" + " do not have lvalues."); Visit(Ex, Pred, Dst); + } } } @@ -1819,7 +1885,7 @@ bool GRExprEngine::InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, if (!FD) return false; - if (!FD->getBody(FD)) + if (!FD->hasBody(FD)) return false; // Now we have the definition of the callee, create a CallEnter node. @@ -1940,7 +2006,8 @@ void GRExprEngine::VisitCall(CallExpr* CE, ExplodedNode* Pred, // Finally, perform the post-condition check of the CallExpr and store // the created nodes in 'Dst'. - + // If the callee returns a reference and we want an rvalue, skip this check + // and do the load. if (!(!asLValue && CalleeReturnsReference(CE))) { CheckerVisit(CE, Dst, DstTmp3, false); return; @@ -2380,7 +2447,7 @@ void GRExprEngine::VisitCast(CastExpr *CastE, Expr *Ex, ExplodedNode *Pred, case CastExpr::CK_AnyPointerToObjCPointerCast: case CastExpr::CK_AnyPointerToBlockPointerCast: case CastExpr::CK_DerivedToBase: - case CastExpr::CK_UncheckedDerivedToBase: + case CastExpr::CK_UncheckedDerivedToBase: { // Delegate to SValuator to process. for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I) { ExplodedNode* N = *I; @@ -2391,10 +2458,24 @@ void GRExprEngine::VisitCast(CastExpr *CastE, Expr *Ex, ExplodedNode *Pred, MakeNode(Dst, CastE, N, state); } return; - - default: - llvm::errs() << "Cast kind " << CastE->getCastKind() << " not handled.\n"; - assert(0); + } + + // Various C++ casts that are not handled yet. + case CastExpr::CK_Dynamic: + case CastExpr::CK_ToUnion: + case CastExpr::CK_BaseToDerived: + case CastExpr::CK_NullToMemberPointer: + case CastExpr::CK_BaseToDerivedMemberPointer: + case CastExpr::CK_DerivedToBaseMemberPointer: + case CastExpr::CK_UserDefinedConversion: + case CastExpr::CK_ConstructorConversion: + case CastExpr::CK_VectorSplat: + case CastExpr::CK_MemberPointerToBoolean: { + SaveAndRestore<bool> OldSink(Builder->BuildSinks); + Builder->BuildSinks = true; + MakeNode(Dst, CastE, Pred, GetState(Pred)); + return; + } } } @@ -2615,9 +2696,38 @@ void GRExprEngine::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr* Ex, // sizeof(void) == 1 byte. amt = CharUnits::One(); } - else if (!T.getTypePtr()->isConstantSizeType()) { - // FIXME: Add support for VLAs. - Dst.Add(Pred); + else if (!T->isConstantSizeType()) { + assert(T->isVariableArrayType() && "Unknown non-constant-sized type."); + + // FIXME: Add support for VLA type arguments, not just VLA expressions. + // When that happens, we should probably refactor VLASizeChecker's code. + if (Ex->isArgumentType()) { + Dst.Add(Pred); + return; + } + + // Get the size by getting the extent of the sub-expression. + // First, visit the sub-expression to find its region. + Expr *Arg = Ex->getArgumentExpr(); + ExplodedNodeSet Tmp; + VisitLValue(Arg, Pred, Tmp); + + for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { + const GRState* state = GetState(*I); + const MemRegion *MR = state->getSVal(Arg).getAsRegion(); + + // If the subexpression can't be resolved to a region, we don't know + // anything about its size. Just leave the state as is and continue. + if (!MR) { + Dst.Add(*I); + continue; + } + + // The result is the extent of the VLA. + SVal Extent = cast<SubRegion>(MR)->getExtent(ValMgr); + MakeNode(Dst, Ex, *I, state->BindExpr(Ex, Extent)); + } + return; } else if (T->getAs<ObjCObjectType>()) { @@ -2749,7 +2859,7 @@ void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, ExplodedNode* Pred, return; } - case UnaryOperator::Plus: assert (!asLValue); // FALL-THROUGH. + case UnaryOperator::Plus: assert(!asLValue); // FALL-THROUGH. case UnaryOperator::Extension: { // Unary "+" is a no-op, similar to a parentheses. We still have places @@ -2759,7 +2869,11 @@ void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, ExplodedNode* Pred, Expr* Ex = U->getSubExpr()->IgnoreParens(); ExplodedNodeSet Tmp; - Visit(Ex, Pred, Tmp); + + if (asLValue) + VisitLValue(Ex, Pred, Tmp); + else + Visit(Ex, Pred, Tmp); for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { const GRState* state = GetState(*I); diff --git a/lib/Checker/GRExprEngineExperimentalChecks.cpp b/lib/Checker/GRExprEngineExperimentalChecks.cpp index 6066a1c74d33..d138e81c4691 100644 --- a/lib/Checker/GRExprEngineExperimentalChecks.cpp +++ b/lib/Checker/GRExprEngineExperimentalChecks.cpp @@ -23,6 +23,8 @@ void clang::RegisterExperimentalChecks(GRExprEngine &Eng) { // within GRExprEngine. RegisterPthreadLockChecker(Eng); RegisterMallocChecker(Eng); + RegisterStreamChecker(Eng); + RegisterCStringChecker(Eng); } void clang::RegisterExperimentalInternalChecks(GRExprEngine &Eng) { @@ -38,4 +40,5 @@ void clang::RegisterExperimentalInternalChecks(GRExprEngine &Eng) { RegisterCastToStructChecker(Eng); RegisterCastSizeChecker(Eng); RegisterArrayBoundChecker(Eng); + } diff --git a/lib/Checker/GRExprEngineExperimentalChecks.h b/lib/Checker/GRExprEngineExperimentalChecks.h index 9a9da32e556e..7d1eb77f9fd6 100644 --- a/lib/Checker/GRExprEngineExperimentalChecks.h +++ b/lib/Checker/GRExprEngineExperimentalChecks.h @@ -19,8 +19,11 @@ namespace clang { class GRExprEngine; +void RegisterCStringChecker(GRExprEngine &Eng); void RegisterPthreadLockChecker(GRExprEngine &Eng); void RegisterMallocChecker(GRExprEngine &Eng); +void RegisterStreamChecker(GRExprEngine &Eng); +void RegisterIdempotentOperationChecker(GRExprEngine &Eng); } // end clang namespace #endif diff --git a/lib/Checker/GRExprEngineInternalChecks.h b/lib/Checker/GRExprEngineInternalChecks.h index 335b85e308e0..f91a759b3299 100644 --- a/lib/Checker/GRExprEngineInternalChecks.h +++ b/lib/Checker/GRExprEngineInternalChecks.h @@ -34,8 +34,8 @@ void RegisterNoReturnFunctionChecker(GRExprEngine &Eng); void RegisterPointerArithChecker(GRExprEngine &Eng); void RegisterPointerSubChecker(GRExprEngine &Eng); void RegisterReturnPointerRangeChecker(GRExprEngine &Eng); -void RegisterReturnStackAddressChecker(GRExprEngine &Eng); void RegisterReturnUndefChecker(GRExprEngine &Eng); +void RegisterStackAddrLeakChecker(GRExprEngine &Eng); void RegisterUndefBranchChecker(GRExprEngine &Eng); void RegisterUndefCapturedBlockVarChecker(GRExprEngine &Eng); void RegisterUndefResultChecker(GRExprEngine &Eng); diff --git a/lib/Checker/GRState.cpp b/lib/Checker/GRState.cpp index b16e922776e5..9e584b56148c 100644 --- a/lib/Checker/GRState.cpp +++ b/lib/Checker/GRState.cpp @@ -34,7 +34,7 @@ GRStateManager::~GRStateManager() { } const GRState* -GRStateManager::RemoveDeadBindings(const GRState* state, Stmt* Loc, +GRStateManager::RemoveDeadBindings(const GRState* state, const StackFrameContext *LCtx, SymbolReaper& SymReaper) { @@ -47,11 +47,11 @@ GRStateManager::RemoveDeadBindings(const GRState* state, Stmt* Loc, llvm::SmallVector<const MemRegion*, 10> RegionRoots; GRState NewState = *state; - NewState.Env = EnvMgr.RemoveDeadBindings(NewState.Env, Loc, SymReaper, + NewState.Env = EnvMgr.RemoveDeadBindings(NewState.Env, SymReaper, state, RegionRoots); // Clean up the store. - const GRState *s = StoreMgr->RemoveDeadBindings(NewState, Loc, LCtx, + const GRState *s = StoreMgr->RemoveDeadBindings(NewState, LCtx, SymReaper, RegionRoots); return ConstraintMgr->RemoveDeadBindings(s, SymReaper); @@ -343,28 +343,3 @@ bool GRState::scanReachableSymbols(const MemRegion * const *I, } return true; } - -//===----------------------------------------------------------------------===// -// Queries. -//===----------------------------------------------------------------------===// - -bool GRStateManager::isEqual(const GRState* state, const Expr* Ex, - const llvm::APSInt& Y) { - - SVal V = state->getSVal(Ex); - - if (loc::ConcreteInt* X = dyn_cast<loc::ConcreteInt>(&V)) - return X->getValue() == Y; - - if (nonloc::ConcreteInt* X = dyn_cast<nonloc::ConcreteInt>(&V)) - return X->getValue() == Y; - - if (SymbolRef Sym = V.getAsSymbol()) - return ConstraintMgr->isEqual(state, Sym, Y); - - return false; -} - -bool GRStateManager::isEqual(const GRState* state, const Expr* Ex, uint64_t x) { - return isEqual(state, Ex, getBasicVals().getValue(x, Ex->getType())); -} diff --git a/lib/Checker/HTMLDiagnostics.cpp b/lib/Checker/HTMLDiagnostics.cpp new file mode 100644 index 000000000000..ff9867fb5f16 --- /dev/null +++ b/lib/Checker/HTMLDiagnostics.cpp @@ -0,0 +1,577 @@ +//===--- HTMLDiagnostics.cpp - HTML Diagnostics for Paths ----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the HTMLDiagnostics object. +// +//===----------------------------------------------------------------------===// + +#include "clang/Checker/PathDiagnosticClients.h" +#include "clang/Checker/BugReporter/PathDiagnostic.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/Basic/SourceManager.h" +#include "clang/Basic/FileManager.h" +#include "clang/Rewrite/Rewriter.h" +#include "clang/Rewrite/HTMLRewrite.h" +#include "clang/Lex/Lexer.h" +#include "clang/Lex/Preprocessor.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/System/Path.h" + +using namespace clang; + +//===----------------------------------------------------------------------===// +// Boilerplate. +//===----------------------------------------------------------------------===// + +namespace { + +class HTMLDiagnostics : public PathDiagnosticClient { + llvm::sys::Path Directory, FilePrefix; + bool createdDir, noDir; + const Preprocessor &PP; + std::vector<const PathDiagnostic*> BatchedDiags; +public: + HTMLDiagnostics(const std::string& prefix, const Preprocessor &pp); + + virtual ~HTMLDiagnostics() { FlushDiagnostics(NULL); } + + virtual void FlushDiagnostics(llvm::SmallVectorImpl<std::string> *FilesMade); + + virtual void HandlePathDiagnostic(const PathDiagnostic* D); + + virtual llvm::StringRef getName() const { + return "HTMLDiagnostics"; + } + + unsigned ProcessMacroPiece(llvm::raw_ostream& os, + const PathDiagnosticMacroPiece& P, + unsigned num); + + void HandlePiece(Rewriter& R, FileID BugFileID, + const PathDiagnosticPiece& P, unsigned num, unsigned max); + + void HighlightRange(Rewriter& R, FileID BugFileID, SourceRange Range, + const char *HighlightStart = "<span class=\"mrange\">", + const char *HighlightEnd = "</span>"); + + void ReportDiag(const PathDiagnostic& D, + llvm::SmallVectorImpl<std::string> *FilesMade); +}; + +} // end anonymous namespace + +HTMLDiagnostics::HTMLDiagnostics(const std::string& prefix, + const Preprocessor &pp) + : Directory(prefix), FilePrefix(prefix), createdDir(false), noDir(false), + PP(pp) { + // All html files begin with "report" + FilePrefix.appendComponent("report"); +} + +PathDiagnosticClient* +clang::CreateHTMLDiagnosticClient(const std::string& prefix, + const Preprocessor &PP) { + return new HTMLDiagnostics(prefix, PP); +} + +//===----------------------------------------------------------------------===// +// Report processing. +//===----------------------------------------------------------------------===// + +void HTMLDiagnostics::HandlePathDiagnostic(const PathDiagnostic* D) { + if (!D) + return; + + if (D->empty()) { + delete D; + return; + } + + const_cast<PathDiagnostic*>(D)->flattenLocations(); + BatchedDiags.push_back(D); +} + +void +HTMLDiagnostics::FlushDiagnostics(llvm::SmallVectorImpl<std::string> *FilesMade) +{ + while (!BatchedDiags.empty()) { + const PathDiagnostic* D = BatchedDiags.back(); + BatchedDiags.pop_back(); + ReportDiag(*D, FilesMade); + delete D; + } + + BatchedDiags.clear(); +} + +void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D, + llvm::SmallVectorImpl<std::string> *FilesMade){ + // Create the HTML directory if it is missing. + if (!createdDir) { + createdDir = true; + std::string ErrorMsg; + Directory.createDirectoryOnDisk(true, &ErrorMsg); + + if (!Directory.isDirectory()) { + llvm::errs() << "warning: could not create directory '" + << Directory.str() << "'\n" + << "reason: " << ErrorMsg << '\n'; + + noDir = true; + + return; + } + } + + if (noDir) + return; + + const SourceManager &SMgr = D.begin()->getLocation().getManager(); + FileID FID; + + // Verify that the entire path is from the same FileID. + for (PathDiagnostic::const_iterator I = D.begin(), E = D.end(); I != E; ++I) { + FullSourceLoc L = I->getLocation().asLocation().getInstantiationLoc(); + + if (FID.isInvalid()) { + FID = SMgr.getFileID(L); + } else if (SMgr.getFileID(L) != FID) + return; // FIXME: Emit a warning? + + // Check the source ranges. + for (PathDiagnosticPiece::range_iterator RI=I->ranges_begin(), + RE=I->ranges_end(); RI!=RE; ++RI) { + + SourceLocation L = SMgr.getInstantiationLoc(RI->getBegin()); + + if (!L.isFileID() || SMgr.getFileID(L) != FID) + return; // FIXME: Emit a warning? + + L = SMgr.getInstantiationLoc(RI->getEnd()); + + if (!L.isFileID() || SMgr.getFileID(L) != FID) + return; // FIXME: Emit a warning? + } + } + + if (FID.isInvalid()) + return; // FIXME: Emit a warning? + + // Create a new rewriter to generate HTML. + Rewriter R(const_cast<SourceManager&>(SMgr), PP.getLangOptions()); + + // Process the path. + unsigned n = D.size(); + unsigned max = n; + + for (PathDiagnostic::const_reverse_iterator I=D.rbegin(), E=D.rend(); + I!=E; ++I, --n) + HandlePiece(R, FID, *I, n, max); + + // Add line numbers, header, footer, etc. + + // unsigned FID = R.getSourceMgr().getMainFileID(); + html::EscapeText(R, FID); + html::AddLineNumbers(R, FID); + + // If we have a preprocessor, relex the file and syntax highlight. + // We might not have a preprocessor if we come from a deserialized AST file, + // for example. + + html::SyntaxHighlight(R, FID, PP); + html::HighlightMacros(R, FID, PP); + + // Get the full directory name of the analyzed file. + + const FileEntry* Entry = SMgr.getFileEntryForID(FID); + + // This is a cludge; basically we want to append either the full + // working directory if we have no directory information. This is + // a work in progress. + + std::string DirName = ""; + + if (!llvm::sys::Path(Entry->getName()).isAbsolute()) { + llvm::sys::Path P = llvm::sys::Path::GetCurrentDirectory(); + DirName = P.str() + "/"; + } + + // Add the name of the file as an <h1> tag. + + { + std::string s; + llvm::raw_string_ostream os(s); + + os << "<!-- REPORTHEADER -->\n" + << "<h3>Bug Summary</h3>\n<table class=\"simpletable\">\n" + "<tr><td class=\"rowname\">File:</td><td>" + << html::EscapeText(DirName) + << html::EscapeText(Entry->getName()) + << "</td></tr>\n<tr><td class=\"rowname\">Location:</td><td>" + "<a href=\"#EndPath\">line " + << (*D.rbegin()).getLocation().asLocation().getInstantiationLineNumber() + << ", column " + << (*D.rbegin()).getLocation().asLocation().getInstantiationColumnNumber() + << "</a></td></tr>\n" + "<tr><td class=\"rowname\">Description:</td><td>" + << D.getDescription() << "</td></tr>\n"; + + // Output any other meta data. + + for (PathDiagnostic::meta_iterator I=D.meta_begin(), E=D.meta_end(); + I!=E; ++I) { + os << "<tr><td></td><td>" << html::EscapeText(*I) << "</td></tr>\n"; + } + + os << "</table>\n<!-- REPORTSUMMARYEXTRA -->\n" + "<h3>Annotated Source Code</h3>\n"; + + R.InsertTextBefore(SMgr.getLocForStartOfFile(FID), os.str()); + } + + // Embed meta-data tags. + { + std::string s; + llvm::raw_string_ostream os(s); + + const std::string& BugDesc = D.getDescription(); + if (!BugDesc.empty()) + os << "\n<!-- BUGDESC " << BugDesc << " -->\n"; + + const std::string& BugType = D.getBugType(); + if (!BugType.empty()) + os << "\n<!-- BUGTYPE " << BugType << " -->\n"; + + const std::string& BugCategory = D.getCategory(); + if (!BugCategory.empty()) + os << "\n<!-- BUGCATEGORY " << BugCategory << " -->\n"; + + os << "\n<!-- BUGFILE " << DirName << Entry->getName() << " -->\n"; + + os << "\n<!-- BUGLINE " + << D.back()->getLocation().asLocation().getInstantiationLineNumber() + << " -->\n"; + + os << "\n<!-- BUGPATHLENGTH " << D.size() << " -->\n"; + + // Mark the end of the tags. + os << "\n<!-- BUGMETAEND -->\n"; + + // Insert the text. + R.InsertTextBefore(SMgr.getLocForStartOfFile(FID), os.str()); + } + + // Add CSS, header, and footer. + + html::AddHeaderFooterInternalBuiltinCSS(R, FID, Entry->getName()); + + // Get the rewrite buffer. + const RewriteBuffer *Buf = R.getRewriteBufferFor(FID); + + if (!Buf) { + llvm::errs() << "warning: no diagnostics generated for main file.\n"; + return; + } + + // Create a path for the target HTML file. + llvm::sys::Path F(FilePrefix); + F.makeUnique(false, NULL); + + // Rename the file with an HTML extension. + llvm::sys::Path H(F); + H.appendSuffix("html"); + F.renamePathOnDisk(H, NULL); + + std::string ErrorMsg; + llvm::raw_fd_ostream os(H.c_str(), ErrorMsg); + + if (!ErrorMsg.empty()) { + llvm::errs() << "warning: could not create file '" << F.str() + << "'\n"; + return; + } + + if (FilesMade) + FilesMade->push_back(H.getLast()); + + // Emit the HTML to disk. + for (RewriteBuffer::iterator I = Buf->begin(), E = Buf->end(); I!=E; ++I) + os << *I; +} + +void HTMLDiagnostics::HandlePiece(Rewriter& R, FileID BugFileID, + const PathDiagnosticPiece& P, + unsigned num, unsigned max) { + + // For now, just draw a box above the line in question, and emit the + // warning. + FullSourceLoc Pos = P.getLocation().asLocation(); + + if (!Pos.isValid()) + return; + + SourceManager &SM = R.getSourceMgr(); + assert(&Pos.getManager() == &SM && "SourceManagers are different!"); + std::pair<FileID, unsigned> LPosInfo = SM.getDecomposedInstantiationLoc(Pos); + + if (LPosInfo.first != BugFileID) + return; + + const llvm::MemoryBuffer *Buf = SM.getBuffer(LPosInfo.first); + const char* FileStart = Buf->getBufferStart(); + + // Compute the column number. Rewind from the current position to the start + // of the line. + unsigned ColNo = SM.getColumnNumber(LPosInfo.first, LPosInfo.second); + const char *TokInstantiationPtr =Pos.getInstantiationLoc().getCharacterData(); + const char *LineStart = TokInstantiationPtr-ColNo; + + // Compute LineEnd. + const char *LineEnd = TokInstantiationPtr; + const char* FileEnd = Buf->getBufferEnd(); + while (*LineEnd != '\n' && LineEnd != FileEnd) + ++LineEnd; + + // Compute the margin offset by counting tabs and non-tabs. + unsigned PosNo = 0; + for (const char* c = LineStart; c != TokInstantiationPtr; ++c) + PosNo += *c == '\t' ? 8 : 1; + + // Create the html for the message. + + const char *Kind = 0; + switch (P.getKind()) { + case PathDiagnosticPiece::Event: Kind = "Event"; break; + case PathDiagnosticPiece::ControlFlow: Kind = "Control"; break; + // Setting Kind to "Control" is intentional. + case PathDiagnosticPiece::Macro: Kind = "Control"; break; + } + + std::string sbuf; + llvm::raw_string_ostream os(sbuf); + + os << "\n<tr><td class=\"num\"></td><td class=\"line\"><div id=\""; + + if (num == max) + os << "EndPath"; + else + os << "Path" << num; + + os << "\" class=\"msg"; + if (Kind) + os << " msg" << Kind; + os << "\" style=\"margin-left:" << PosNo << "ex"; + + // Output a maximum size. + if (!isa<PathDiagnosticMacroPiece>(P)) { + // Get the string and determining its maximum substring. + const std::string& Msg = P.getString(); + unsigned max_token = 0; + unsigned cnt = 0; + unsigned len = Msg.size(); + + for (std::string::const_iterator I=Msg.begin(), E=Msg.end(); I!=E; ++I) + switch (*I) { + default: + ++cnt; + continue; + case ' ': + case '\t': + case '\n': + if (cnt > max_token) max_token = cnt; + cnt = 0; + } + + if (cnt > max_token) + max_token = cnt; + + // Determine the approximate size of the message bubble in em. + unsigned em; + const unsigned max_line = 120; + + if (max_token >= max_line) + em = max_token / 2; + else { + unsigned characters = max_line; + unsigned lines = len / max_line; + + if (lines > 0) { + for (; characters > max_token; --characters) + if (len / characters > lines) { + ++characters; + break; + } + } + + em = characters / 2; + } + + if (em < max_line/2) + os << "; max-width:" << em << "em"; + } + else + os << "; max-width:100em"; + + os << "\">"; + + if (max > 1) { + os << "<table class=\"msgT\"><tr><td valign=\"top\">"; + os << "<div class=\"PathIndex"; + if (Kind) os << " PathIndex" << Kind; + os << "\">" << num << "</div>"; + os << "</td><td>"; + } + + if (const PathDiagnosticMacroPiece *MP = + dyn_cast<PathDiagnosticMacroPiece>(&P)) { + + os << "Within the expansion of the macro '"; + + // Get the name of the macro by relexing it. + { + FullSourceLoc L = MP->getLocation().asLocation().getInstantiationLoc(); + assert(L.isFileID()); + llvm::StringRef BufferInfo = L.getBufferData(); + const char* MacroName = L.getDecomposedLoc().second + BufferInfo.data(); + Lexer rawLexer(L, PP.getLangOptions(), BufferInfo.begin(), + MacroName, BufferInfo.end()); + + Token TheTok; + rawLexer.LexFromRawLexer(TheTok); + for (unsigned i = 0, n = TheTok.getLength(); i < n; ++i) + os << MacroName[i]; + } + + os << "':\n"; + + if (max > 1) + os << "</td></tr></table>"; + + // Within a macro piece. Write out each event. + ProcessMacroPiece(os, *MP, 0); + } + else { + os << html::EscapeText(P.getString()); + + if (max > 1) + os << "</td></tr></table>"; + } + + os << "</div></td></tr>"; + + // Insert the new html. + unsigned DisplayPos = LineEnd - FileStart; + SourceLocation Loc = + SM.getLocForStartOfFile(LPosInfo.first).getFileLocWithOffset(DisplayPos); + + R.InsertTextBefore(Loc, os.str()); + + // Now highlight the ranges. + for (const SourceRange *I = P.ranges_begin(), *E = P.ranges_end(); + I != E; ++I) + HighlightRange(R, LPosInfo.first, *I); + +#if 0 + // If there is a code insertion hint, insert that code. + // FIXME: This code is disabled because it seems to mangle the HTML + // output. I'm leaving it here because it's generally the right idea, + // but needs some help from someone more familiar with the rewriter. + for (const FixItHint *Hint = P.fixit_begin(), *HintEnd = P.fixit_end(); + Hint != HintEnd; ++Hint) { + if (Hint->RemoveRange.isValid()) { + HighlightRange(R, LPosInfo.first, Hint->RemoveRange, + "<span class=\"CodeRemovalHint\">", "</span>"); + } + if (Hint->InsertionLoc.isValid()) { + std::string EscapedCode = html::EscapeText(Hint->CodeToInsert, true); + EscapedCode = "<span class=\"CodeInsertionHint\">" + EscapedCode + + "</span>"; + R.InsertTextBefore(Hint->InsertionLoc, EscapedCode); + } + } +#endif +} + +static void EmitAlphaCounter(llvm::raw_ostream& os, unsigned n) { + unsigned x = n % ('z' - 'a'); + n /= 'z' - 'a'; + + if (n > 0) + EmitAlphaCounter(os, n); + + os << char('a' + x); +} + +unsigned HTMLDiagnostics::ProcessMacroPiece(llvm::raw_ostream& os, + const PathDiagnosticMacroPiece& P, + unsigned num) { + + for (PathDiagnosticMacroPiece::const_iterator I=P.begin(), E=P.end(); + I!=E; ++I) { + + if (const PathDiagnosticMacroPiece *MP = + dyn_cast<PathDiagnosticMacroPiece>(*I)) { + num = ProcessMacroPiece(os, *MP, num); + continue; + } + + if (PathDiagnosticEventPiece *EP = dyn_cast<PathDiagnosticEventPiece>(*I)) { + os << "<div class=\"msg msgEvent\" style=\"width:94%; " + "margin-left:5px\">" + "<table class=\"msgT\"><tr>" + "<td valign=\"top\"><div class=\"PathIndex PathIndexEvent\">"; + EmitAlphaCounter(os, num++); + os << "</div></td><td valign=\"top\">" + << html::EscapeText(EP->getString()) + << "</td></tr></table></div>\n"; + } + } + + return num; +} + +void HTMLDiagnostics::HighlightRange(Rewriter& R, FileID BugFileID, + SourceRange Range, + const char *HighlightStart, + const char *HighlightEnd) { + SourceManager &SM = R.getSourceMgr(); + const LangOptions &LangOpts = R.getLangOpts(); + + SourceLocation InstantiationStart = SM.getInstantiationLoc(Range.getBegin()); + unsigned StartLineNo = SM.getInstantiationLineNumber(InstantiationStart); + + SourceLocation InstantiationEnd = SM.getInstantiationLoc(Range.getEnd()); + unsigned EndLineNo = SM.getInstantiationLineNumber(InstantiationEnd); + + if (EndLineNo < StartLineNo) + return; + + if (SM.getFileID(InstantiationStart) != BugFileID || + SM.getFileID(InstantiationEnd) != BugFileID) + return; + + // Compute the column number of the end. + unsigned EndColNo = SM.getInstantiationColumnNumber(InstantiationEnd); + unsigned OldEndColNo = EndColNo; + + if (EndColNo) { + // Add in the length of the token, so that we cover multi-char tokens. + EndColNo += Lexer::MeasureTokenLength(Range.getEnd(), SM, LangOpts)-1; + } + + // Highlight the range. Make the span tag the outermost tag for the + // selected range. + + SourceLocation E = + InstantiationEnd.getFileLocWithOffset(EndColNo - OldEndColNo); + + html::HighlightRange(R, InstantiationStart, E, HighlightStart, HighlightEnd); +} diff --git a/lib/Checker/IdempotentOperationChecker.cpp b/lib/Checker/IdempotentOperationChecker.cpp new file mode 100644 index 000000000000..6ed18417a2c2 --- /dev/null +++ b/lib/Checker/IdempotentOperationChecker.cpp @@ -0,0 +1,454 @@ +//==- IdempotentOperationChecker.cpp - Idempotent Operations ----*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a set of path-sensitive checks for idempotent and/or +// tautological operations. Each potential operation is checked along all paths +// to see if every path results in a pointless operation. +// +-------------------------------------------+ +// |Table of idempotent/tautological operations| +// +-------------------------------------------+ +//+--------------------------------------------------------------------------+ +//|Operator | x op x | x op 1 | 1 op x | x op 0 | 0 op x | x op ~0 | ~0 op x | +//+--------------------------------------------------------------------------+ +// +, += | | | | x | x | | +// -, -= | | | | x | -x | | +// *, *= | | x | x | 0 | 0 | | +// /, /= | 1 | x | | N/A | 0 | | +// &, &= | x | | | 0 | 0 | x | x +// |, |= | x | | | x | x | ~0 | ~0 +// ^, ^= | 0 | | | x | x | | +// <<, <<= | | | | x | 0 | | +// >>, >>= | | | | x | 0 | | +// || | 1 | 1 | 1 | x | x | 1 | 1 +// && | 1 | x | x | 0 | 0 | x | x +// = | x | | | | | | +// == | 1 | | | | | | +// >= | 1 | | | | | | +// <= | 1 | | | | | | +// > | 0 | | | | | | +// < | 0 | | | | | | +// != | 0 | | | | | | +//===----------------------------------------------------------------------===// +// +// Ways to reduce false positives (that need to be implemented): +// - Don't flag downsizing casts +// - Improved handling of static/global variables +// - Per-block marking of incomplete analysis +// - Handling ~0 values +// - False positives involving silencing unused variable warnings +// +// Other things TODO: +// - Improved error messages +// - Handle mixed assumptions (which assumptions can belong together?) +// - Finer grained false positive control (levels) + +#include "GRExprEngineExperimentalChecks.h" +#include "clang/Checker/BugReporter/BugType.h" +#include "clang/Checker/PathSensitive/CheckerVisitor.h" +#include "clang/Checker/PathSensitive/SVals.h" +#include "clang/AST/Stmt.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/Support/ErrorHandling.h" + +using namespace clang; + +namespace { +class IdempotentOperationChecker + : public CheckerVisitor<IdempotentOperationChecker> { + public: + static void *getTag(); + void PreVisitBinaryOperator(CheckerContext &C, const BinaryOperator *B); + void VisitEndAnalysis(ExplodedGraph &G, BugReporter &B, + bool hasWorkRemaining); + + private: + // Our assumption about a particular operation. + enum Assumption { Possible, Impossible, Equal, LHSis1, RHSis1, LHSis0, + RHSis0 }; + + void UpdateAssumption(Assumption &A, const Assumption &New); + + /// contains* - Useful recursive methods to see if a statement contains an + /// element somewhere. Used in static analysis to reduce false positives. + static bool containsMacro(const Stmt *S); + static bool containsEnum(const Stmt *S); + static bool containsBuiltinOffsetOf(const Stmt *S); + static bool containsZeroConstant(const Stmt *S); + static bool containsOneConstant(const Stmt *S); + template <class T> static bool containsStmt(const Stmt *S) { + if (isa<T>(S)) + return true; + + for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end(); + ++I) + if (const Stmt *child = *I) + if (containsStmt<T>(child)) + return true; + + return false; + } + + // Hash table + typedef llvm::DenseMap<const BinaryOperator *, Assumption> AssumptionMap; + AssumptionMap hash; +}; +} + +void *IdempotentOperationChecker::getTag() { + static int x = 0; + return &x; +} + +void clang::RegisterIdempotentOperationChecker(GRExprEngine &Eng) { + Eng.registerCheck(new IdempotentOperationChecker()); +} + +void IdempotentOperationChecker::PreVisitBinaryOperator( + CheckerContext &C, + const BinaryOperator *B) { + // Find or create an entry in the hash for this BinaryOperator instance + AssumptionMap::iterator i = hash.find(B); + Assumption &A = i == hash.end() ? hash[B] : i->second; + + // If we had to create an entry, initialise the value to Possible + if (i == hash.end()) + A = Possible; + + // If we already have visited this node on a path that does not contain an + // idempotent operation, return immediately. + if (A == Impossible) + return; + + // Skip binary operators containing common false positives + if (containsMacro(B) || containsEnum(B) || containsStmt<SizeOfAlignOfExpr>(B) + || containsZeroConstant(B) || containsOneConstant(B) + || containsBuiltinOffsetOf(B)) { + A = Impossible; + return; + } + + const Expr *LHS = B->getLHS(); + const Expr *RHS = B->getRHS(); + + const GRState *state = C.getState(); + + SVal LHSVal = state->getSVal(LHS); + SVal RHSVal = state->getSVal(RHS); + + // If either value is unknown, we can't be 100% sure of all paths. + if (LHSVal.isUnknownOrUndef() || RHSVal.isUnknownOrUndef()) { + A = Impossible; + return; + } + BinaryOperator::Opcode Op = B->getOpcode(); + + // Dereference the LHS SVal if this is an assign operation + switch (Op) { + default: + break; + + // Fall through intentional + case BinaryOperator::AddAssign: + case BinaryOperator::SubAssign: + case BinaryOperator::MulAssign: + case BinaryOperator::DivAssign: + case BinaryOperator::AndAssign: + case BinaryOperator::OrAssign: + case BinaryOperator::XorAssign: + case BinaryOperator::ShlAssign: + case BinaryOperator::ShrAssign: + case BinaryOperator::Assign: + // Assign statements have one extra level of indirection + if (!isa<Loc>(LHSVal)) { + A = Impossible; + return; + } + LHSVal = state->getSVal(cast<Loc>(LHSVal)); + } + + + // We now check for various cases which result in an idempotent operation. + + // x op x + switch (Op) { + default: + break; // We don't care about any other operators. + + // Fall through intentional + case BinaryOperator::SubAssign: + case BinaryOperator::DivAssign: + case BinaryOperator::AndAssign: + case BinaryOperator::OrAssign: + case BinaryOperator::XorAssign: + case BinaryOperator::Assign: + case BinaryOperator::Sub: + case BinaryOperator::Div: + case BinaryOperator::And: + case BinaryOperator::Or: + case BinaryOperator::Xor: + case BinaryOperator::LOr: + case BinaryOperator::LAnd: + if (LHSVal != RHSVal) + break; + UpdateAssumption(A, Equal); + return; + } + + // x op 1 + switch (Op) { + default: + break; // We don't care about any other operators. + + // Fall through intentional + case BinaryOperator::MulAssign: + case BinaryOperator::DivAssign: + case BinaryOperator::Mul: + case BinaryOperator::Div: + case BinaryOperator::LOr: + case BinaryOperator::LAnd: + if (!RHSVal.isConstant(1)) + break; + UpdateAssumption(A, RHSis1); + return; + } + + // 1 op x + switch (Op) { + default: + break; // We don't care about any other operators. + + // Fall through intentional + case BinaryOperator::MulAssign: + case BinaryOperator::Mul: + case BinaryOperator::LOr: + case BinaryOperator::LAnd: + if (!LHSVal.isConstant(1)) + break; + UpdateAssumption(A, LHSis1); + return; + } + + // x op 0 + switch (Op) { + default: + break; // We don't care about any other operators. + + // Fall through intentional + case BinaryOperator::AddAssign: + case BinaryOperator::SubAssign: + case BinaryOperator::MulAssign: + case BinaryOperator::AndAssign: + case BinaryOperator::OrAssign: + case BinaryOperator::XorAssign: + case BinaryOperator::Add: + case BinaryOperator::Sub: + case BinaryOperator::Mul: + case BinaryOperator::And: + case BinaryOperator::Or: + case BinaryOperator::Xor: + case BinaryOperator::Shl: + case BinaryOperator::Shr: + case BinaryOperator::LOr: + case BinaryOperator::LAnd: + if (!RHSVal.isConstant(0)) + break; + UpdateAssumption(A, RHSis0); + return; + } + + // 0 op x + switch (Op) { + default: + break; // We don't care about any other operators. + + // Fall through intentional + //case BinaryOperator::AddAssign: // Common false positive + case BinaryOperator::SubAssign: // Check only if unsigned + case BinaryOperator::MulAssign: + case BinaryOperator::DivAssign: + case BinaryOperator::AndAssign: + //case BinaryOperator::OrAssign: // Common false positive + //case BinaryOperator::XorAssign: // Common false positive + case BinaryOperator::ShlAssign: + case BinaryOperator::ShrAssign: + case BinaryOperator::Add: + case BinaryOperator::Sub: + case BinaryOperator::Mul: + case BinaryOperator::Div: + case BinaryOperator::And: + case BinaryOperator::Or: + case BinaryOperator::Xor: + case BinaryOperator::Shl: + case BinaryOperator::Shr: + case BinaryOperator::LOr: + case BinaryOperator::LAnd: + if (!LHSVal.isConstant(0)) + break; + UpdateAssumption(A, LHSis0); + return; + } + + // If we get to this point, there has been a valid use of this operation. + A = Impossible; +} + +void IdempotentOperationChecker::VisitEndAnalysis(ExplodedGraph &G, + BugReporter &B, + bool hasWorkRemaining) { + // If there is any work remaining we cannot be 100% sure about our warnings + if (hasWorkRemaining) + return; + + // Iterate over the hash to see if we have any paths with definite + // idempotent operations. + for (AssumptionMap::const_iterator i = + hash.begin(); i != hash.end(); ++i) { + if (i->second != Impossible) { + // Select the error message. + const char *msg = 0; + switch (i->second) { + case Equal: + msg = "idempotent operation; both operands are always equal in value"; + break; + case LHSis1: + msg = "idempotent operation; the left operand is always 1"; + break; + case RHSis1: + msg = "idempotent operation; the right operand is always 1"; + break; + case LHSis0: + msg = "idempotent operation; the left operand is always 0"; + break; + case RHSis0: + msg = "idempotent operation; the right operand is always 0"; + break; + case Possible: + llvm_unreachable("Operation was never marked with an assumption"); + case Impossible: + llvm_unreachable(0); + } + + // Create the SourceRange Arrays + SourceRange S[2] = { i->first->getLHS()->getSourceRange(), + i->first->getRHS()->getSourceRange() }; + B.EmitBasicReport("Idempotent operation", msg, i->first->getOperatorLoc(), + S, 2); + } + } +} + +// Updates the current assumption given the new assumption +inline void IdempotentOperationChecker::UpdateAssumption(Assumption &A, + const Assumption &New) { + switch (A) { + // If we don't currently have an assumption, set it + case Possible: + A = New; + return; + + // If we have determined that a valid state happened, ignore the new + // assumption. + case Impossible: + return; + + // Any other case means that we had a different assumption last time. We don't + // currently support mixing assumptions for diagnostic reasons, so we set + // our assumption to be impossible. + default: + A = Impossible; + return; + } +} + +// Recursively find any substatements containing macros +bool IdempotentOperationChecker::containsMacro(const Stmt *S) { + if (S->getLocStart().isMacroID()) + return true; + + if (S->getLocEnd().isMacroID()) + return true; + + for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end(); + ++I) + if (const Stmt *child = *I) + if (containsMacro(child)) + return true; + + return false; +} + +// Recursively find any substatements containing enum constants +bool IdempotentOperationChecker::containsEnum(const Stmt *S) { + const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(S); + + if (DR && isa<EnumConstantDecl>(DR->getDecl())) + return true; + + for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end(); + ++I) + if (const Stmt *child = *I) + if (containsEnum(child)) + return true; + + return false; +} + +// Recursively find any substatements containing __builtin_offset_of +bool IdempotentOperationChecker::containsBuiltinOffsetOf(const Stmt *S) { + const UnaryOperator *UO = dyn_cast<UnaryOperator>(S); + + if (UO && UO->getOpcode() == UnaryOperator::OffsetOf) + return true; + + for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end(); + ++I) + if (const Stmt *child = *I) + if (containsBuiltinOffsetOf(child)) + return true; + + return false; +} + +bool IdempotentOperationChecker::containsZeroConstant(const Stmt *S) { + const IntegerLiteral *IL = dyn_cast<IntegerLiteral>(S); + if (IL && IL->getValue() == 0) + return true; + + const FloatingLiteral *FL = dyn_cast<FloatingLiteral>(S); + if (FL && FL->getValue().isZero()) + return true; + + for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end(); + ++I) + if (const Stmt *child = *I) + if (containsZeroConstant(child)) + return true; + + return false; +} + +bool IdempotentOperationChecker::containsOneConstant(const Stmt *S) { + const IntegerLiteral *IL = dyn_cast<IntegerLiteral>(S); + if (IL && IL->getValue() == 1) + return true; + + const FloatingLiteral *FL = dyn_cast<FloatingLiteral>(S); + const llvm::APFloat one(1.0); + if (FL && FL->getValue().compare(one) == llvm::APFloat::cmpEqual) + return true; + + for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end(); + ++I) + if (const Stmt *child = *I) + if (containsOneConstant(child)) + return true; + + return false; +} + diff --git a/lib/Checker/LLVMConventionsChecker.cpp b/lib/Checker/LLVMConventionsChecker.cpp index 39ded431279c..0576f08e4e01 100644 --- a/lib/Checker/LLVMConventionsChecker.cpp +++ b/lib/Checker/LLVMConventionsChecker.cpp @@ -34,13 +34,15 @@ static bool IsLLVMStringRef(QualType T) { "class llvm::StringRef"; } -static bool InStdNamespace(const Decl *D) { +/// Check whether the declaration is semantically inside the top-level +/// namespace named by ns. +static bool InNamespace(const Decl *D, const llvm::StringRef &NS) { const DeclContext *DC = D->getDeclContext(); const NamespaceDecl *ND = dyn_cast<NamespaceDecl>(D->getDeclContext()); if (!ND) return false; const IdentifierInfo *II = ND->getIdentifier(); - if (!II || II->getName() != "std") + if (!II || !II->getName().equals(NS)) return false; DC = ND->getDeclContext(); return isa<TranslationUnitDecl>(DC); @@ -56,50 +58,26 @@ static bool IsStdString(QualType T) { const TypedefDecl *TD = TT->getDecl(); - if (!InStdNamespace(TD)) + if (!InNamespace(TD, "std")) return false; return TD->getName() == "string"; } -static bool InClangNamespace(const Decl *D) { - const DeclContext *DC = D->getDeclContext(); - const NamespaceDecl *ND = dyn_cast<NamespaceDecl>(D->getDeclContext()); - if (!ND) - return false; - const IdentifierInfo *II = ND->getIdentifier(); - if (!II || II->getName() != "clang") - return false; - DC = ND->getDeclContext(); - return isa<TranslationUnitDecl>(DC); -} - -static bool InLLVMNamespace(const Decl *D) { - const DeclContext *DC = D->getDeclContext(); - const NamespaceDecl *ND = dyn_cast<NamespaceDecl>(D->getDeclContext()); - if (!ND) - return false; - const IdentifierInfo *II = ND->getIdentifier(); - if (!II || II->getName() != "llvm") - return false; - DC = ND->getDeclContext(); - return isa<TranslationUnitDecl>(DC); -} - static bool IsClangType(const RecordDecl *RD) { - return RD->getName() == "Type" && InClangNamespace(RD); + return RD->getName() == "Type" && InNamespace(RD, "clang"); } static bool IsClangDecl(const RecordDecl *RD) { - return RD->getName() == "Decl" && InClangNamespace(RD); + return RD->getName() == "Decl" && InNamespace(RD, "clang"); } static bool IsClangStmt(const RecordDecl *RD) { - return RD->getName() == "Stmt" && InClangNamespace(RD); + return RD->getName() == "Stmt" && InNamespace(RD, "clang"); } -static bool isClangAttr(const RecordDecl *RD) { - return RD->getName() == "Attr" && InClangNamespace(RD); +static bool IsClangAttr(const RecordDecl *RD) { + return RD->getName() == "Attr" && InNamespace(RD, "clang"); } static bool IsStdVector(QualType T) { @@ -110,7 +88,7 @@ static bool IsStdVector(QualType T) { TemplateName TM = TS->getTemplateName(); TemplateDecl *TD = TM.getAsTemplateDecl(); - if (!TD || !InStdNamespace(TD)) + if (!TD || !InNamespace(TD, "std")) return false; return TD->getName() == "vector"; @@ -124,7 +102,7 @@ static bool IsSmallVector(QualType T) { TemplateName TM = TS->getTemplateName(); TemplateDecl *TD = TM.getAsTemplateDecl(); - if (!TD || !InLLVMNamespace(TD)) + if (!TD || !InNamespace(TD, "llvm")) return false; return TD->getName() == "SmallVector"; @@ -214,7 +192,7 @@ static bool AllocatesMemory(QualType T) { // This type checking could be sped up via dynamic programming. static bool IsPartOfAST(const CXXRecordDecl *R) { - if (IsClangStmt(R) || IsClangType(R) || IsClangDecl(R) || isClangAttr(R)) + if (IsClangStmt(R) || IsClangType(R) || IsClangDecl(R) || IsClangAttr(R)) return true; for (CXXRecordDecl::base_class_const_iterator I = R->bases_begin(), @@ -316,7 +294,7 @@ static void ScanCodeDecls(DeclContext *DC, BugReporter &BR) { Decl *D = *I; - if (D->getBody()) + if (D->hasBody()) CheckStringRefAssignedTemporary(D, BR); if (CXXRecordDecl *R = dyn_cast<CXXRecordDecl>(D)) diff --git a/lib/Checker/Makefile b/lib/Checker/Makefile index c45ab294dec4..1bc652916403 100644 --- a/lib/Checker/Makefile +++ b/lib/Checker/Makefile @@ -11,11 +11,9 @@ # ##===----------------------------------------------------------------------===## -LEVEL = ../../../.. +CLANG_LEVEL := ../.. LIBRARYNAME := clangChecker BUILD_ARCHIVE = 1 -CPP.Flags += -I$(PROJ_SRC_DIR)/../../include -I$(PROJ_OBJ_DIR)/../../include - -include $(LEVEL)/Makefile.common +include $(CLANG_LEVEL)/Makefile diff --git a/lib/Checker/MallocChecker.cpp b/lib/Checker/MallocChecker.cpp index 086dbd8fdd36..dcc21ca38619 100644 --- a/lib/Checker/MallocChecker.cpp +++ b/lib/Checker/MallocChecker.cpp @@ -59,15 +59,16 @@ class MallocChecker : public CheckerVisitor<MallocChecker> { BuiltinBug *BT_DoubleFree; BuiltinBug *BT_Leak; BuiltinBug *BT_UseFree; - IdentifierInfo *II_malloc, *II_free, *II_realloc; + BuiltinBug *BT_BadFree; + IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc; public: MallocChecker() - : BT_DoubleFree(0), BT_Leak(0), BT_UseFree(0), - II_malloc(0), II_free(0), II_realloc(0) {} + : BT_DoubleFree(0), BT_Leak(0), BT_UseFree(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); - void EvalDeadSymbols(CheckerContext &C,const Stmt *S,SymbolReaper &SymReaper); + void EvalDeadSymbols(CheckerContext &C, 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); @@ -76,12 +77,24 @@ public: private: void MallocMem(CheckerContext &C, const CallExpr *CE); const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE, - const Expr *SizeEx, const GRState *state); + const Expr *SizeEx, SVal Init, + const GRState *state) { + return MallocMemAux(C, CE, state->getSVal(SizeEx), Init, state); + } + const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE, + SVal SizeEx, SVal Init, + const GRState *state); + void FreeMem(CheckerContext &C, const CallExpr *CE); const GRState *FreeMemAux(CheckerContext &C, const CallExpr *CE, const GRState *state); void ReallocMem(CheckerContext &C, const CallExpr *CE); + void CallocMem(CheckerContext &C, const CallExpr *CE); + + bool SummarizeValue(llvm::raw_ostream& os, SVal V); + bool SummarizeRegion(llvm::raw_ostream& os, const MemRegion *MR); + void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range); }; } // end anonymous namespace @@ -120,6 +133,8 @@ bool MallocChecker::EvalCallExpr(CheckerContext &C, const CallExpr *CE) { II_free = &Ctx.Idents.get("free"); if (!II_realloc) II_realloc = &Ctx.Idents.get("realloc"); + if (!II_calloc) + II_calloc = &Ctx.Idents.get("calloc"); if (FD->getIdentifier() == II_malloc) { MallocMem(C, CE); @@ -136,30 +151,44 @@ bool MallocChecker::EvalCallExpr(CheckerContext &C, const CallExpr *CE) { return true; } + if (FD->getIdentifier() == II_calloc) { + CallocMem(C, CE); + return true; + } + return false; } void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) { - const GRState *state = MallocMemAux(C, CE, CE->getArg(0), C.getState()); + const GRState *state = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), + C.getState()); C.addTransition(state); } const GRState *MallocChecker::MallocMemAux(CheckerContext &C, const CallExpr *CE, - const Expr *SizeEx, + SVal Size, SVal Init, const GRState *state) { unsigned Count = C.getNodeBuilder().getCurrentBlockCount(); ValueManager &ValMgr = C.getValueManager(); + // Set the return value. SVal RetVal = ValMgr.getConjuredSymbolVal(NULL, CE, CE->getType(), Count); + state = state->BindExpr(CE, RetVal); - SVal Size = state->getSVal(SizeEx); + // Fill the region with the initialization value. + state = state->bindDefault(RetVal, Init); - state = C.getEngine().getStoreManager().setExtent(state, RetVal.getAsRegion(), - Size); + // Set the region's extent equal to the Size parameter. + const SymbolicRegion *R = cast<SymbolicRegion>(RetVal.getAsRegion()); + DefinedOrUnknownSVal Extent = R->getExtent(ValMgr); + DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size); + + SValuator &SVator = ValMgr.getSValuator(); + DefinedOrUnknownSVal ExtentMatchesSize = + SVator.EvalEQ(state, Extent, DefinedSize); + state = state->Assume(ExtentMatchesSize, true); - state = state->BindExpr(CE, RetVal); - SymbolRef Sym = RetVal.getAsLocSymbol(); assert(Sym); // Set the symbol's state to Allocated. @@ -175,18 +204,59 @@ void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) { const GRState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE, const GRState *state) { - SVal ArgVal = state->getSVal(CE->getArg(0)); + const Expr *ArgExpr = CE->getArg(0); + SVal ArgVal = state->getSVal(ArgExpr); // If ptr is NULL, no operation is preformed. if (ArgVal.isZeroConstant()) return state; + + // Unknown values could easily be okay + // Undefined values are handled elsewhere + if (ArgVal.isUnknownOrUndef()) + return state; - SymbolRef Sym = ArgVal.getAsLocSymbol(); - + const MemRegion *R = ArgVal.getAsRegion(); + + // Nonlocs can't be freed, of course. + // Non-region locations (labels and fixed addresses) also shouldn't be freed. + if (!R) { + ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); + return NULL; + } + + R = R->StripCasts(); + + // Blocks might show up as heap data, but should not be free()d + if (isa<BlockDataRegion>(R)) { + ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); + return NULL; + } + + const MemSpaceRegion *MS = R->getMemorySpace(); + + // Parameters, locals, statics, and globals shouldn't be freed. + if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) { + // FIXME: at the time this code was written, malloc() regions were + // represented by conjured symbols, which are all in UnknownSpaceRegion. + // This means that there isn't actually anything from HeapSpaceRegion + // that should be freed, even though we allow it here. + // Of course, free() can work on memory allocated outside the current + // function, so UnknownSpaceRegion is always a possibility. + // False negatives are better than false positives. + + ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); + return NULL; + } + + const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R); // Various cases could lead to non-symbol values here. - if (!Sym) + // For now, ignore them. + if (!SR) return state; + SymbolRef Sym = SR->getSymbol(); + const RefState *RS = state->get<RegionState>(Sym); // If the symbol has not been tracked, return. This is possible when free() is @@ -214,6 +284,135 @@ const GRState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE, return state->set<RegionState>(Sym, RefState::getReleased(CE)); } +bool MallocChecker::SummarizeValue(llvm::raw_ostream& os, SVal V) { + if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V)) + os << "an integer (" << IntVal->getValue() << ")"; + else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V)) + os << "a constant address (" << ConstAddr->getValue() << ")"; + else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V)) + os << "the address of the label '" + << Label->getLabel()->getID()->getName() + << "'"; + else + return false; + + return true; +} + +bool MallocChecker::SummarizeRegion(llvm::raw_ostream& os, + const MemRegion *MR) { + switch (MR->getKind()) { + case MemRegion::FunctionTextRegionKind: { + const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl(); + if (FD) + os << "the address of the function '" << FD << "'"; + else + os << "the address of a function"; + return true; + } + case MemRegion::BlockTextRegionKind: + os << "block text"; + return true; + case MemRegion::BlockDataRegionKind: + // FIXME: where the block came from? + os << "a block"; + return true; + default: { + const MemSpaceRegion *MS = MR->getMemorySpace(); + + switch (MS->getKind()) { + case MemRegion::StackLocalsSpaceRegionKind: { + const VarRegion *VR = dyn_cast<VarRegion>(MR); + const VarDecl *VD; + if (VR) + VD = VR->getDecl(); + else + VD = NULL; + + if (VD) + os << "the address of the local variable '" << VD->getName() << "'"; + else + os << "the address of a local stack variable"; + return true; + } + case MemRegion::StackArgumentsSpaceRegionKind: { + const VarRegion *VR = dyn_cast<VarRegion>(MR); + const VarDecl *VD; + if (VR) + VD = VR->getDecl(); + else + VD = NULL; + + if (VD) + os << "the address of the parameter '" << VD->getName() << "'"; + else + os << "the address of a parameter"; + return true; + } + case MemRegion::NonStaticGlobalSpaceRegionKind: + case MemRegion::StaticGlobalSpaceRegionKind: { + const VarRegion *VR = dyn_cast<VarRegion>(MR); + const VarDecl *VD; + if (VR) + VD = VR->getDecl(); + else + VD = NULL; + + if (VD) { + if (VD->isStaticLocal()) + os << "the address of the static variable '" << VD->getName() << "'"; + else + os << "the address of the global variable '" << VD->getName() << "'"; + } else + os << "the address of a global variable"; + return true; + } + default: + return false; + } + } + } +} + +void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal, + SourceRange range) { + ExplodedNode *N = C.GenerateSink(); + if (N) { + if (!BT_BadFree) + BT_BadFree = new BuiltinBug("Bad free"); + + llvm::SmallString<100> buf; + llvm::raw_svector_ostream os(buf); + + const MemRegion *MR = ArgVal.getAsRegion(); + if (MR) { + while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR)) + MR = ER->getSuperRegion(); + + // Special case for alloca() + if (isa<AllocaRegion>(MR)) + os << "Argument to free() was allocated by alloca(), not malloc()"; + else { + os << "Argument to free() is "; + if (SummarizeRegion(os, MR)) + os << ", which is not memory allocated by malloc()"; + else + os << "not memory allocated by malloc()"; + } + } else { + os << "Argument to free() is "; + if (SummarizeValue(os, ArgVal)) + os << ", which is not memory allocated by malloc()"; + else + os << "not memory allocated by malloc()"; + } + + EnhancedBugReport *R = new EnhancedBugReport(*BT_BadFree, os.str(), N); + R->addRange(range); + C.EmitReport(R); + } +} + void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) { const GRState *state = C.getState(); const Expr *Arg0 = CE->getArg(0); @@ -234,7 +433,8 @@ void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) { if (Sym) stateEqual = stateEqual->set<RegionState>(Sym, RefState::getReleased(CE)); - const GRState *stateMalloc = MallocMemAux(C, CE, CE->getArg(1), stateEqual); + const GRState *stateMalloc = MallocMemAux(C, CE, CE->getArg(1), + UndefinedVal(), stateEqual); C.addTransition(stateMalloc); } @@ -256,15 +456,31 @@ void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) { if (stateFree) { // FIXME: We should copy the content of the original buffer. const GRState *stateRealloc = MallocMemAux(C, CE, CE->getArg(1), - stateFree); + UnknownVal(), stateFree); C.addTransition(stateRealloc); } } } } -void MallocChecker::EvalDeadSymbols(CheckerContext &C, const Stmt *S, - SymbolReaper &SymReaper) { +void MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + + ValueManager &ValMgr = C.getValueManager(); + SValuator &SVator = C.getSValuator(); + + SVal Count = state->getSVal(CE->getArg(0)); + SVal EleSize = state->getSVal(CE->getArg(1)); + SVal TotalSize = SVator.EvalBinOp(state, BinaryOperator::Mul, Count, EleSize, + ValMgr.getContext().getSizeType()); + + SVal Zero = ValMgr.makeZeroVal(ValMgr.getContext().CharTy); + + state = MallocMemAux(C, CE, TotalSize, Zero, state); + C.addTransition(state); +} + +void MallocChecker::EvalDeadSymbols(CheckerContext &C,SymbolReaper &SymReaper) { for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(), E = SymReaper.dead_end(); I != E; ++I) { SymbolRef Sym = *I; diff --git a/lib/Checker/MemRegion.cpp b/lib/Checker/MemRegion.cpp index 575458c9dc79..9cfeb7ae2b5c 100644 --- a/lib/Checker/MemRegion.cpp +++ b/lib/Checker/MemRegion.cpp @@ -14,6 +14,7 @@ //===----------------------------------------------------------------------===// #include "clang/Checker/PathSensitive/MemRegion.h" +#include "clang/Checker/PathSensitive/ValueManager.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/Support/BumpVector.h" #include "clang/AST/CharUnits.h" @@ -29,22 +30,22 @@ template<typename RegionTy> struct MemRegionManagerTrait; template <typename RegionTy, typename A1> RegionTy* MemRegionManager::getRegion(const A1 a1) { - + const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion = MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1); - + llvm::FoldingSetNodeID ID; RegionTy::ProfileRegion(ID, a1, superRegion); void* InsertPos; RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, InsertPos)); - + if (!R) { R = (RegionTy*) A.Allocate<RegionTy>(); new (R) RegionTy(a1, superRegion); Regions.InsertNode(R, InsertPos); } - + return R; } @@ -56,72 +57,72 @@ RegionTy* MemRegionManager::getSubRegion(const A1 a1, void* InsertPos; RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, InsertPos)); - + if (!R) { R = (RegionTy*) A.Allocate<RegionTy>(); new (R) RegionTy(a1, superRegion); Regions.InsertNode(R, InsertPos); } - + return R; } template <typename RegionTy, typename A1, typename A2> RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) { - + const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion = MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2); - + llvm::FoldingSetNodeID ID; RegionTy::ProfileRegion(ID, a1, a2, superRegion); void* InsertPos; RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, InsertPos)); - + if (!R) { R = (RegionTy*) A.Allocate<RegionTy>(); new (R) RegionTy(a1, a2, superRegion); Regions.InsertNode(R, InsertPos); } - + return R; } template <typename RegionTy, typename A1, typename A2> RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const MemRegion *superRegion) { - + llvm::FoldingSetNodeID ID; RegionTy::ProfileRegion(ID, a1, a2, superRegion); void* InsertPos; RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, InsertPos)); - + if (!R) { R = (RegionTy*) A.Allocate<RegionTy>(); new (R) RegionTy(a1, a2, superRegion); Regions.InsertNode(R, InsertPos); } - + return R; } template <typename RegionTy, typename A1, typename A2, typename A3> RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3, const MemRegion *superRegion) { - + llvm::FoldingSetNodeID ID; RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion); void* InsertPos; RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, InsertPos)); - + if (!R) { R = (RegionTy*) A.Allocate<RegionTy>(); new (R) RegionTy(a1, a2, a3, superRegion); Regions.InsertNode(R, InsertPos); } - + return R; } @@ -171,6 +172,53 @@ const StackFrameContext *VarRegion::getStackFrame() const { } //===----------------------------------------------------------------------===// +// Region extents. +//===----------------------------------------------------------------------===// + +DefinedOrUnknownSVal DeclRegion::getExtent(ValueManager& ValMgr) const { + ASTContext& Ctx = ValMgr.getContext(); + QualType T = getDesugaredValueType(Ctx); + + if (isa<VariableArrayType>(T)) + return nonloc::SymbolVal(ValMgr.getSymbolManager().getExtentSymbol(this)); + if (isa<IncompleteArrayType>(T)) + return UnknownVal(); + + CharUnits Size = Ctx.getTypeSizeInChars(T); + QualType SizeTy = Ctx.getSizeType(); + return ValMgr.makeIntVal(Size.getQuantity(), SizeTy); +} + +DefinedOrUnknownSVal FieldRegion::getExtent(ValueManager& ValMgr) const { + DefinedOrUnknownSVal Extent = DeclRegion::getExtent(ValMgr); + + // A zero-length array at the end of a struct often stands for dynamically- + // allocated extra memory. + if (Extent.isZeroConstant()) { + ASTContext& Ctx = ValMgr.getContext(); + QualType T = getDesugaredValueType(Ctx); + + if (isa<ConstantArrayType>(T)) + return UnknownVal(); + } + + return Extent; +} + +DefinedOrUnknownSVal AllocaRegion::getExtent(ValueManager& ValMgr) const { + return nonloc::SymbolVal(ValMgr.getSymbolManager().getExtentSymbol(this)); +} + +DefinedOrUnknownSVal SymbolicRegion::getExtent(ValueManager& ValMgr) const { + return nonloc::SymbolVal(ValMgr.getSymbolManager().getExtentSymbol(this)); +} + +DefinedOrUnknownSVal StringRegion::getExtent(ValueManager& ValMgr) const { + QualType SizeTy = ValMgr.getContext().getSizeType(); + return ValMgr.makeIntVal(getStringLiteral()->getByteLength()+1, SizeTy); +} + +//===----------------------------------------------------------------------===// // FoldingSet profiling. //===----------------------------------------------------------------------===// @@ -183,6 +231,11 @@ void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const { ID.AddPointer(getStackFrame()); } +void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const { + ID.AddInteger((unsigned)getKind()); + ID.AddPointer(getCodeRegion()); +} + void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const StringLiteral* Str, const MemRegion* superRegion) { @@ -226,7 +279,7 @@ void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const { CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion); } - + void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl* D, const MemRegion* superRegion, Kind k) { ID.AddInteger((unsigned) k); @@ -349,7 +402,6 @@ void BlockDataRegion::dumpToStream(llvm::raw_ostream& os) const { os << "block_data{" << BC << '}'; } - void CompoundLiteralRegion::dumpToStream(llvm::raw_ostream& os) const { // FIXME: More elaborate pretty-printing. os << "{ " << (void*) CL << " }"; @@ -368,6 +420,10 @@ void FieldRegion::dumpToStream(llvm::raw_ostream& os) const { os << superRegion << "->" << getDecl(); } +void NonStaticGlobalSpaceRegion::dumpToStream(llvm::raw_ostream &os) const { + os << "NonStaticGlobalSpaceRegion"; +} + void ObjCIvarRegion::dumpToStream(llvm::raw_ostream& os) const { os << "ivar{" << superRegion << ',' << getDecl() << '}'; } @@ -392,6 +448,10 @@ void RegionRawOffset::dumpToStream(llvm::raw_ostream& os) const { os << "raw_offset{" << getRegion() << ',' << getByteOffset() << '}'; } +void StaticGlobalSpaceRegion::dumpToStream(llvm::raw_ostream &os) const { + os << "StaticGlobalsMemSpace{" << CR << '}'; +} + //===----------------------------------------------------------------------===// // MemRegionManager methods. //===----------------------------------------------------------------------===// @@ -412,7 +472,7 @@ const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) { region = (REG*) A.Allocate<REG>(); new (region) REG(this, a); } - + return region; } @@ -442,8 +502,18 @@ MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) { return R; } -const GlobalsSpaceRegion *MemRegionManager::getGlobalsRegion() { - return LazyAllocate(globals); +const GlobalsSpaceRegion +*MemRegionManager::getGlobalsRegion(const CodeTextRegion *CR) { + if (!CR) + return LazyAllocate(globals); + + StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR]; + if (R) + return R; + + R = A.Allocate<StaticGlobalSpaceRegion>(); + new (R) StaticGlobalSpaceRegion(this, CR); + return R; } const HeapSpaceRegion *MemRegionManager::getHeapRegion() { @@ -462,7 +532,7 @@ const MemSpaceRegion *MemRegionManager::getCodeRegion() { // Constructing regions. //===----------------------------------------------------------------------===// -const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str) { +const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){ return getSubRegion<StringRegion>(Str, getGlobalsRegion()); } @@ -470,7 +540,9 @@ const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D, const LocationContext *LC) { const MemRegion *sReg = 0; - if (D->hasLocalStorage()) { + if (D->hasGlobalStorage() && !D->isStaticLocal()) + sReg = getGlobalsRegion(); + else { // FIXME: Once we implement scope handling, we will need to properly lookup // 'D' to the proper LocationContext. const DeclContext *DC = D->getDeclContext(); @@ -479,15 +551,32 @@ const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D, if (!STC) sReg = getUnknownRegion(); else { - sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D) - ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC)) - : static_cast<const MemRegion*>(getStackLocalsRegion(STC)); + if (D->hasLocalStorage()) { + sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D) + ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC)) + : static_cast<const MemRegion*>(getStackLocalsRegion(STC)); + } + else { + assert(D->isStaticLocal()); + const Decl *D = STC->getDecl(); + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) + sReg = getGlobalsRegion(getFunctionTextRegion(FD)); + else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) { + const BlockTextRegion *BTR = + getBlockTextRegion(BD, + C.getCanonicalType(BD->getSignatureAsWritten()->getType()), + STC->getAnalysisContext()); + sReg = getGlobalsRegion(BTR); + } + else { + // FIXME: For ObjC-methods, we need a new CodeTextRegion. For now + // just use the main global memspace. + sReg = getGlobalsRegion(); + } + } } } - else { - sReg = getGlobalsRegion(); - } - + return getSubRegion<VarRegion>(D, sReg); } @@ -500,10 +589,10 @@ const BlockDataRegion * MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC, const LocationContext *LC) { const MemRegion *sReg = 0; - - if (LC) { + + if (LC) { // FIXME: Once we implement scope handling, we want the parent region - // to be the scope. + // to be the scope. const StackFrameContext *STC = LC->getCurrentStackFrame(); assert(STC); sReg = getStackLocalsRegion(STC); @@ -520,9 +609,9 @@ MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC, const CompoundLiteralRegion* MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr* CL, const LocationContext *LC) { - + const MemRegion *sReg = 0; - + if (CL->isFileScope()) sReg = getGlobalsRegion(); else { @@ -530,7 +619,7 @@ MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr* CL, assert(STC); sReg = getStackLocalsRegion(STC); } - + return getSubRegion<CompoundLiteralRegion>(CL, sReg); } @@ -749,24 +838,24 @@ void BlockDataRegion::LazyInitializeReferencedVars() { AnalysisContext *AC = getCodeRegion()->getAnalysisContext(); AnalysisContext::referenced_decls_iterator I, E; llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl()); - + if (I == E) { ReferencedVars = (void*) 0x1; return; } - + MemRegionManager &MemMgr = *getMemRegionManager(); llvm::BumpPtrAllocator &A = MemMgr.getAllocator(); BumpVectorContext BC(A); - + typedef BumpVector<const MemRegion*> VarVec; VarVec *BV = (VarVec*) A.Allocate<VarVec>(); new (BV) VarVec(BC, E - I); - + for ( ; I != E; ++I) { const VarDecl *VD = *I; const VarRegion *VR = 0; - + if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage()) VR = MemMgr.getVarRegion(VD, this); else { @@ -776,11 +865,11 @@ void BlockDataRegion::LazyInitializeReferencedVars() { VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion()); } } - + assert(VR); BV->push_back(VR, BC); } - + ReferencedVars = BV; } @@ -790,7 +879,7 @@ BlockDataRegion::referenced_vars_begin() const { BumpVector<const MemRegion*> *Vec = static_cast<BumpVector<const MemRegion*>*>(ReferencedVars); - + return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ? NULL : Vec->begin()); } @@ -801,7 +890,7 @@ BlockDataRegion::referenced_vars_end() const { BumpVector<const MemRegion*> *Vec = static_cast<BumpVector<const MemRegion*>*>(ReferencedVars); - + return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ? NULL : Vec->end()); } diff --git a/lib/Checker/OSAtomicChecker.cpp b/lib/Checker/OSAtomicChecker.cpp index e743528e2399..1ea1bd98d6dc 100644 --- a/lib/Checker/OSAtomicChecker.cpp +++ b/lib/Checker/OSAtomicChecker.cpp @@ -100,7 +100,13 @@ bool OSAtomicChecker::EvalOSAtomicCompareAndSwap(CheckerContext &C, const GRState *state = C.getState(); ExplodedNodeSet Tmp; SVal location = state->getSVal(theValueExpr); - // Here we should use the value type of the region as the load type. + // Here we should use the value type of the region as the load type, because + // we are simulating the semantics of the function, not the semantics of + // passing argument. So the type of theValue expr is not we are loading. + // But usually the type of the varregion is not the type we want either, + // we still need to do a CastRetrievedVal in store manager. So actually this + // LoadTy specifying can be omitted. But we put it here to emphasize the + // semantics. QualType LoadTy; if (const TypedRegion *TR = dyn_cast_or_null<TypedRegion>(location.getAsRegion())) { diff --git a/lib/Checker/PathDiagnostic.cpp b/lib/Checker/PathDiagnostic.cpp index 963923c9ad10..cf05a7df67f3 100644 --- a/lib/Checker/PathDiagnostic.cpp +++ b/lib/Checker/PathDiagnostic.cpp @@ -107,7 +107,7 @@ void PathDiagnosticClient::HandleDiagnostic(Diagnostic::Level DiagLevel, new PathDiagnosticEventPiece(Info.getLocation(), StrC.str()); for (unsigned i = 0, e = Info.getNumRanges(); i != e; ++i) - P->addRange(Info.getRange(i)); + P->addRange(Info.getRange(i).getAsRange()); for (unsigned i = 0, e = Info.getNumFixItHints(); i != e; ++i) P->addFixItHint(Info.getFixItHint(i)); D->push_front(P); @@ -181,15 +181,8 @@ PathDiagnosticRange PathDiagnosticLocation::asRange() const { if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) return MD->getSourceRange(); if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { - // FIXME: We would like to always get the function body, even - // when it needs to be de-serialized, but getting the - // ASTContext here requires significant changes. - if (Stmt *Body = FD->getBody()) { - if (CompoundStmt *CS = dyn_cast<CompoundStmt>(Body)) - return CS->getSourceRange(); - else - return cast<CXXTryStmt>(Body)->getSourceRange(); - } + if (Stmt *Body = FD->getBody()) + return Body->getSourceRange(); } else { SourceLocation L = D->getLocation(); diff --git a/lib/Checker/PlistDiagnostics.cpp b/lib/Checker/PlistDiagnostics.cpp new file mode 100644 index 000000000000..13accbbff8c7 --- /dev/null +++ b/lib/Checker/PlistDiagnostics.cpp @@ -0,0 +1,471 @@ +//===--- PlistDiagnostics.cpp - Plist Diagnostics for Paths -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the PlistDiagnostics object. +// +//===----------------------------------------------------------------------===// + +#include "clang/Checker/PathDiagnosticClients.h" +#include "clang/Checker/BugReporter/PathDiagnostic.h" +#include "clang/Basic/SourceManager.h" +#include "clang/Basic/FileManager.h" +#include "clang/Lex/Preprocessor.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/Casting.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +using namespace clang; +using llvm::cast; + +typedef llvm::DenseMap<FileID, unsigned> FIDMap; + +namespace clang { + class Preprocessor; +} + +namespace { +struct CompareDiagnostics { + // Compare if 'X' is "<" than 'Y'. + bool operator()(const PathDiagnostic *X, const PathDiagnostic *Y) const { + // First compare by location + const FullSourceLoc &XLoc = X->getLocation().asLocation(); + const FullSourceLoc &YLoc = Y->getLocation().asLocation(); + if (XLoc < YLoc) + return true; + if (XLoc != YLoc) + return false; + + // Next, compare by bug type. + llvm::StringRef XBugType = X->getBugType(); + llvm::StringRef YBugType = Y->getBugType(); + if (XBugType < YBugType) + return true; + if (XBugType != YBugType) + return false; + + // Next, compare by bug description. + llvm::StringRef XDesc = X->getDescription(); + llvm::StringRef YDesc = Y->getDescription(); + if (XDesc < YDesc) + return true; + if (XDesc != YDesc) + return false; + + // FIXME: Further refine by comparing PathDiagnosticPieces? + return false; + } +}; +} + +namespace { + class PlistDiagnostics : public PathDiagnosticClient { + std::vector<const PathDiagnostic*> BatchedDiags; + const std::string OutputFile; + const LangOptions &LangOpts; + llvm::OwningPtr<PathDiagnosticClient> SubPD; + bool flushed; + public: + PlistDiagnostics(const std::string& prefix, const LangOptions &LangOpts, + PathDiagnosticClient *subPD); + + ~PlistDiagnostics() { FlushDiagnostics(NULL); } + + void FlushDiagnostics(llvm::SmallVectorImpl<std::string> *FilesMade); + + void HandlePathDiagnostic(const PathDiagnostic* D); + + virtual llvm::StringRef getName() const { + return "PlistDiagnostics"; + } + + PathGenerationScheme getGenerationScheme() const; + bool supportsLogicalOpControlFlow() const { return true; } + bool supportsAllBlockEdges() const { return true; } + virtual bool useVerboseDescription() const { return false; } + }; +} // end anonymous namespace + +PlistDiagnostics::PlistDiagnostics(const std::string& output, + const LangOptions &LO, + PathDiagnosticClient *subPD) + : OutputFile(output), LangOpts(LO), SubPD(subPD), flushed(false) {} + +PathDiagnosticClient* +clang::CreatePlistDiagnosticClient(const std::string& s, const Preprocessor &PP, + PathDiagnosticClient *subPD) { + return new PlistDiagnostics(s, PP.getLangOptions(), subPD); +} + +PathDiagnosticClient::PathGenerationScheme +PlistDiagnostics::getGenerationScheme() const { + if (const PathDiagnosticClient *PD = SubPD.get()) + return PD->getGenerationScheme(); + + return Extensive; +} + +static void AddFID(FIDMap &FIDs, llvm::SmallVectorImpl<FileID> &V, + const SourceManager* SM, SourceLocation L) { + + FileID FID = SM->getFileID(SM->getInstantiationLoc(L)); + FIDMap::iterator I = FIDs.find(FID); + if (I != FIDs.end()) return; + FIDs[FID] = V.size(); + V.push_back(FID); +} + +static unsigned GetFID(const FIDMap& FIDs, const SourceManager &SM, + SourceLocation L) { + FileID FID = SM.getFileID(SM.getInstantiationLoc(L)); + FIDMap::const_iterator I = FIDs.find(FID); + assert(I != FIDs.end()); + return I->second; +} + +static llvm::raw_ostream& Indent(llvm::raw_ostream& o, const unsigned indent) { + for (unsigned i = 0; i < indent; ++i) o << ' '; + return o; +} + +static void EmitLocation(llvm::raw_ostream& o, const SourceManager &SM, + const LangOptions &LangOpts, + SourceLocation L, const FIDMap &FM, + unsigned indent, bool extend = false) { + + FullSourceLoc Loc(SM.getInstantiationLoc(L), const_cast<SourceManager&>(SM)); + + // Add in the length of the token, so that we cover multi-char tokens. + unsigned offset = + extend ? Lexer::MeasureTokenLength(Loc, SM, LangOpts) - 1 : 0; + + Indent(o, indent) << "<dict>\n"; + Indent(o, indent) << " <key>line</key><integer>" + << Loc.getInstantiationLineNumber() << "</integer>\n"; + Indent(o, indent) << " <key>col</key><integer>" + << Loc.getInstantiationColumnNumber() + offset << "</integer>\n"; + Indent(o, indent) << " <key>file</key><integer>" + << GetFID(FM, SM, Loc) << "</integer>\n"; + Indent(o, indent) << "</dict>\n"; +} + +static void EmitLocation(llvm::raw_ostream& o, const SourceManager &SM, + const LangOptions &LangOpts, + const PathDiagnosticLocation &L, const FIDMap& FM, + unsigned indent, bool extend = false) { + EmitLocation(o, SM, LangOpts, L.asLocation(), FM, indent, extend); +} + +static void EmitRange(llvm::raw_ostream& o, const SourceManager &SM, + const LangOptions &LangOpts, + PathDiagnosticRange R, const FIDMap &FM, + unsigned indent) { + Indent(o, indent) << "<array>\n"; + EmitLocation(o, SM, LangOpts, R.getBegin(), FM, indent+1); + EmitLocation(o, SM, LangOpts, R.getEnd(), FM, indent+1, !R.isPoint); + Indent(o, indent) << "</array>\n"; +} + +static llvm::raw_ostream& EmitString(llvm::raw_ostream& o, + const std::string& s) { + o << "<string>"; + for (std::string::const_iterator I=s.begin(), E=s.end(); I!=E; ++I) { + char c = *I; + switch (c) { + default: o << c; break; + case '&': o << "&"; break; + case '<': o << "<"; break; + case '>': o << ">"; break; + case '\'': o << "'"; break; + case '\"': o << """; break; + } + } + o << "</string>"; + return o; +} + +static void ReportControlFlow(llvm::raw_ostream& o, + const PathDiagnosticControlFlowPiece& P, + const FIDMap& FM, + const SourceManager &SM, + const LangOptions &LangOpts, + unsigned indent) { + + Indent(o, indent) << "<dict>\n"; + ++indent; + + Indent(o, indent) << "<key>kind</key><string>control</string>\n"; + + // Emit edges. + Indent(o, indent) << "<key>edges</key>\n"; + ++indent; + Indent(o, indent) << "<array>\n"; + ++indent; + for (PathDiagnosticControlFlowPiece::const_iterator I=P.begin(), E=P.end(); + I!=E; ++I) { + Indent(o, indent) << "<dict>\n"; + ++indent; + Indent(o, indent) << "<key>start</key>\n"; + EmitRange(o, SM, LangOpts, I->getStart().asRange(), FM, indent+1); + Indent(o, indent) << "<key>end</key>\n"; + EmitRange(o, SM, LangOpts, I->getEnd().asRange(), FM, indent+1); + --indent; + Indent(o, indent) << "</dict>\n"; + } + --indent; + Indent(o, indent) << "</array>\n"; + --indent; + + // Output any helper text. + const std::string& s = P.getString(); + if (!s.empty()) { + Indent(o, indent) << "<key>alternate</key>"; + EmitString(o, s) << '\n'; + } + + --indent; + Indent(o, indent) << "</dict>\n"; +} + +static void ReportEvent(llvm::raw_ostream& o, const PathDiagnosticPiece& P, + const FIDMap& FM, + const SourceManager &SM, + const LangOptions &LangOpts, + unsigned indent) { + + Indent(o, indent) << "<dict>\n"; + ++indent; + + Indent(o, indent) << "<key>kind</key><string>event</string>\n"; + + // Output the location. + FullSourceLoc L = P.getLocation().asLocation(); + + Indent(o, indent) << "<key>location</key>\n"; + EmitLocation(o, SM, LangOpts, L, FM, indent); + + // Output the ranges (if any). + PathDiagnosticPiece::range_iterator RI = P.ranges_begin(), + RE = P.ranges_end(); + + if (RI != RE) { + Indent(o, indent) << "<key>ranges</key>\n"; + Indent(o, indent) << "<array>\n"; + ++indent; + for (; RI != RE; ++RI) + EmitRange(o, SM, LangOpts, *RI, FM, indent+1); + --indent; + Indent(o, indent) << "</array>\n"; + } + + // Output the text. + assert(!P.getString().empty()); + Indent(o, indent) << "<key>extended_message</key>\n"; + Indent(o, indent); + EmitString(o, P.getString()) << '\n'; + + // Output the short text. + // FIXME: Really use a short string. + Indent(o, indent) << "<key>message</key>\n"; + EmitString(o, P.getString()) << '\n'; + + // Finish up. + --indent; + Indent(o, indent); o << "</dict>\n"; +} + +static void ReportMacro(llvm::raw_ostream& o, + const PathDiagnosticMacroPiece& P, + const FIDMap& FM, const SourceManager &SM, + const LangOptions &LangOpts, + unsigned indent) { + + for (PathDiagnosticMacroPiece::const_iterator I=P.begin(), E=P.end(); + I!=E; ++I) { + + switch ((*I)->getKind()) { + default: + break; + case PathDiagnosticPiece::Event: + ReportEvent(o, cast<PathDiagnosticEventPiece>(**I), FM, SM, LangOpts, + indent); + break; + case PathDiagnosticPiece::Macro: + ReportMacro(o, cast<PathDiagnosticMacroPiece>(**I), FM, SM, LangOpts, + indent); + break; + } + } +} + +static void ReportDiag(llvm::raw_ostream& o, const PathDiagnosticPiece& P, + const FIDMap& FM, const SourceManager &SM, + const LangOptions &LangOpts) { + + unsigned indent = 4; + + switch (P.getKind()) { + case PathDiagnosticPiece::ControlFlow: + ReportControlFlow(o, cast<PathDiagnosticControlFlowPiece>(P), FM, SM, + LangOpts, indent); + break; + case PathDiagnosticPiece::Event: + ReportEvent(o, cast<PathDiagnosticEventPiece>(P), FM, SM, LangOpts, + indent); + break; + case PathDiagnosticPiece::Macro: + ReportMacro(o, cast<PathDiagnosticMacroPiece>(P), FM, SM, LangOpts, + indent); + break; + } +} + +void PlistDiagnostics::HandlePathDiagnostic(const PathDiagnostic* D) { + if (!D) + return; + + if (D->empty()) { + delete D; + return; + } + + // We need to flatten the locations (convert Stmt* to locations) because + // the referenced statements may be freed by the time the diagnostics + // are emitted. + const_cast<PathDiagnostic*>(D)->flattenLocations(); + BatchedDiags.push_back(D); +} + +void PlistDiagnostics::FlushDiagnostics(llvm::SmallVectorImpl<std::string> + *FilesMade) { + + if (flushed) + return; + + flushed = true; + + // Sort the diagnostics so that they are always emitted in a deterministic + // order. + if (!BatchedDiags.empty()) + std::sort(BatchedDiags.begin(), BatchedDiags.end(), CompareDiagnostics()); + + // Build up a set of FIDs that we use by scanning the locations and + // ranges of the diagnostics. + FIDMap FM; + llvm::SmallVector<FileID, 10> Fids; + const SourceManager* SM = 0; + + if (!BatchedDiags.empty()) + SM = &(*BatchedDiags.begin())->begin()->getLocation().getManager(); + + for (std::vector<const PathDiagnostic*>::iterator DI = BatchedDiags.begin(), + DE = BatchedDiags.end(); DI != DE; ++DI) { + + const PathDiagnostic *D = *DI; + + for (PathDiagnostic::const_iterator I=D->begin(), E=D->end(); I!=E; ++I) { + AddFID(FM, Fids, SM, I->getLocation().asLocation()); + + for (PathDiagnosticPiece::range_iterator RI=I->ranges_begin(), + RE=I->ranges_end(); RI!=RE; ++RI) { + AddFID(FM, Fids, SM, RI->getBegin()); + AddFID(FM, Fids, SM, RI->getEnd()); + } + } + } + + // Open the file. + std::string ErrMsg; + llvm::raw_fd_ostream o(OutputFile.c_str(), ErrMsg); + if (!ErrMsg.empty()) { + llvm::errs() << "warning: could not creat file: " << OutputFile << '\n'; + return; + } + + // Write the plist header. + o << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n" + "<!DOCTYPE plist PUBLIC \"-//Apple Computer//DTD PLIST 1.0//EN\" " + "\"http://www.apple.com/DTDs/PropertyList-1.0.dtd\">\n" + "<plist version=\"1.0\">\n"; + + // Write the root object: a <dict> containing... + // - "files", an <array> mapping from FIDs to file names + // - "diagnostics", an <array> containing the path diagnostics + o << "<dict>\n" + " <key>files</key>\n" + " <array>\n"; + + for (llvm::SmallVectorImpl<FileID>::iterator I=Fids.begin(), E=Fids.end(); + I!=E; ++I) { + o << " "; + EmitString(o, SM->getFileEntryForID(*I)->getName()) << '\n'; + } + + o << " </array>\n" + " <key>diagnostics</key>\n" + " <array>\n"; + + for (std::vector<const PathDiagnostic*>::iterator DI=BatchedDiags.begin(), + DE = BatchedDiags.end(); DI!=DE; ++DI) { + + o << " <dict>\n" + " <key>path</key>\n"; + + const PathDiagnostic *D = *DI; + // Create an owning smart pointer for 'D' just so that we auto-free it + // when we exit this method. + llvm::OwningPtr<PathDiagnostic> OwnedD(const_cast<PathDiagnostic*>(D)); + + o << " <array>\n"; + + for (PathDiagnostic::const_iterator I=D->begin(), E=D->end(); I != E; ++I) + ReportDiag(o, *I, FM, *SM, LangOpts); + + o << " </array>\n"; + + // Output the bug type and bug category. + o << " <key>description</key>"; + EmitString(o, D->getDescription()) << '\n'; + o << " <key>category</key>"; + EmitString(o, D->getCategory()) << '\n'; + o << " <key>type</key>"; + EmitString(o, D->getBugType()) << '\n'; + + // Output the location of the bug. + o << " <key>location</key>\n"; + EmitLocation(o, *SM, LangOpts, D->getLocation(), FM, 2); + + // Output the diagnostic to the sub-diagnostic client, if any. + if (SubPD) { + SubPD->HandlePathDiagnostic(OwnedD.take()); + llvm::SmallVector<std::string, 1> SubFilesMade; + SubPD->FlushDiagnostics(SubFilesMade); + + if (!SubFilesMade.empty()) { + o << " <key>" << SubPD->getName() << "_files</key>\n"; + o << " <array>\n"; + for (size_t i = 0, n = SubFilesMade.size(); i < n ; ++i) + o << " <string>" << SubFilesMade[i] << "</string>\n"; + o << " </array>\n"; + } + } + + // Close up the entry. + o << " </dict>\n"; + } + + o << " </array>\n"; + + // Finish. + o << "</dict>\n</plist>"; + + if (FilesMade) + FilesMade->push_back(OutputFile); + + BatchedDiags.clear(); +} diff --git a/lib/Checker/RangeConstraintManager.cpp b/lib/Checker/RangeConstraintManager.cpp index c904c33e08d2..2a35d326a988 100644 --- a/lib/Checker/RangeConstraintManager.cpp +++ b/lib/Checker/RangeConstraintManager.cpp @@ -105,97 +105,69 @@ public: return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : 0; } - /// AddEQ - Create a new RangeSet with the additional constraint that the - /// value be equal to V. - RangeSet AddEQ(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) { - // Search for a range that includes 'V'. If so, return a new RangeSet - // representing { [V, V] }. - for (PrimRangeSet::iterator i = begin(), e = end(); i!=e; ++i) - if (i->Includes(V)) - return RangeSet(F, V, V); - - return RangeSet(F); - } - - /// AddNE - Create a new RangeSet with the additional constraint that the - /// value be not be equal to V. - RangeSet AddNE(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) { - PrimRangeSet newRanges = ranges; - - // FIXME: We can perhaps enhance ImmutableSet to do this search for us - // in log(N) time using the sorted property of the internal AVL tree. - for (iterator i = begin(), e = end(); i != e; ++i) { - if (i->Includes(V)) { - // Remove the old range. - newRanges = F.Remove(newRanges, *i); - // Split the old range into possibly one or two ranges. - if (V != i->From()) - newRanges = F.Add(newRanges, Range(i->From(), BV.Sub1(V))); - if (V != i->To()) - newRanges = F.Add(newRanges, Range(BV.Add1(V), i->To())); - // All of the ranges are non-overlapping, so we can stop. +private: + void IntersectInRange(BasicValueFactory &BV, Factory &F, + const llvm::APSInt &Lower, + const llvm::APSInt &Upper, + PrimRangeSet &newRanges, + PrimRangeSet::iterator &i, + PrimRangeSet::iterator &e) const { + // There are six cases for each range R in the set: + // 1. R is entirely before the intersection range. + // 2. R is entirely after the intersection range. + // 3. R contains the entire intersection range. + // 4. R starts before the intersection range and ends in the middle. + // 5. R starts in the middle of the intersection range and ends after it. + // 6. R is entirely contained in the intersection range. + // These correspond to each of the conditions below. + for (/* i = begin(), e = end() */; i != e; ++i) { + if (i->To() < Lower) { + continue; + } + if (i->From() > Upper) { break; } - } - - return newRanges; - } - - /// AddNE - Create a new RangeSet with the additional constraint that the - /// value be less than V. - RangeSet AddLT(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) { - PrimRangeSet newRanges = F.GetEmptySet(); - - for (iterator i = begin(), e = end() ; i != e ; ++i) { - if (i->Includes(V) && i->From() < V) - newRanges = F.Add(newRanges, Range(i->From(), BV.Sub1(V))); - else if (i->To() < V) - newRanges = F.Add(newRanges, *i); - } - - return newRanges; - } - - RangeSet AddLE(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) { - PrimRangeSet newRanges = F.GetEmptySet(); - for (iterator i = begin(), e = end(); i != e; ++i) { - // Strictly we should test for includes *V + 1, but no harm is - // done by this formulation - if (i->Includes(V)) - newRanges = F.Add(newRanges, Range(i->From(), V)); - else if (i->To() <= V) - newRanges = F.Add(newRanges, *i); - } - - return newRanges; - } - - RangeSet AddGT(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) { - PrimRangeSet newRanges = F.GetEmptySet(); - - for (PrimRangeSet::iterator i = begin(), e = end(); i != e; ++i) { - if (i->Includes(V) && i->To() > V) - newRanges = F.Add(newRanges, Range(BV.Add1(V), i->To())); - else if (i->From() > V) - newRanges = F.Add(newRanges, *i); + if (i->Includes(Lower)) { + if (i->Includes(Upper)) { + newRanges = F.Add(newRanges, Range(BV.getValue(Lower), + BV.getValue(Upper))); + break; + } else + newRanges = F.Add(newRanges, Range(BV.getValue(Lower), i->To())); + } else { + if (i->Includes(Upper)) { + newRanges = F.Add(newRanges, Range(i->From(), BV.getValue(Upper))); + break; + } else + newRanges = F.Add(newRanges, *i); + } } - - return newRanges; } - RangeSet AddGE(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) { +public: + // Returns a set containing the values in the receiving set, intersected with + // the closed range [Lower, Upper]. Unlike the Range type, this range uses + // modular arithmetic, corresponding to the common treatment of C integer + // overflow. Thus, if the Lower bound is greater than the Upper bound, the + // range is taken to wrap around. This is equivalent to taking the + // intersection with the two ranges [Min, Upper] and [Lower, Max], + // or, alternatively, /removing/ all integers between Upper and Lower. + RangeSet Intersect(BasicValueFactory &BV, Factory &F, + const llvm::APSInt &Lower, + const llvm::APSInt &Upper) const { PrimRangeSet newRanges = F.GetEmptySet(); - for (PrimRangeSet::iterator i = begin(), e = end(); i != e; ++i) { - // Strictly we should test for includes *V - 1, but no harm is - // done by this formulation - if (i->Includes(V)) - newRanges = F.Add(newRanges, Range(V, i->To())); - else if (i->From() >= V) - newRanges = F.Add(newRanges, *i); + PrimRangeSet::iterator i = begin(), e = end(); + if (Lower <= Upper) + IntersectInRange(BV, F, Lower, Upper, newRanges, i, e); + else { + // The order of the next two statements is important! + // IntersectInRange() does not reset the iteration state for i and e. + // Therefore, the lower range most be handled first. + IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e); + IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e); } - return newRanges; } @@ -237,23 +209,29 @@ public: RangeConstraintManager(GRSubEngine &subengine) : SimpleConstraintManager(subengine) {} - const GRState* AssumeSymNE(const GRState* St, SymbolRef sym, - const llvm::APSInt& V); + const GRState* AssumeSymNE(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment); - const GRState* AssumeSymEQ(const GRState* St, SymbolRef sym, - const llvm::APSInt& V); + const GRState* AssumeSymEQ(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment); - const GRState* AssumeSymLT(const GRState* St, SymbolRef sym, - const llvm::APSInt& V); + const GRState* AssumeSymLT(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment); - const GRState* AssumeSymGT(const GRState* St, SymbolRef sym, - const llvm::APSInt& V); + const GRState* AssumeSymGT(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment); - const GRState* AssumeSymGE(const GRState* St, SymbolRef sym, - const llvm::APSInt& V); + const GRState* AssumeSymGE(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment); - const GRState* AssumeSymLE(const GRState* St, SymbolRef sym, - const llvm::APSInt& V); + const GRState* AssumeSymLE(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment); const llvm::APSInt* getSymVal(const GRState* St, SymbolRef sym) const; @@ -303,10 +281,6 @@ RangeConstraintManager::RemoveDeadBindings(const GRState* state, return state->set<ConstraintRange>(CR); } -//===------------------------------------------------------------------------=== -// AssumeSymX methods: public interface for RangeConstraintManager. -//===------------------------------------------------------------------------===/ - RangeSet RangeConstraintManager::GetRange(const GRState *state, SymbolRef sym) { if (ConstraintRangeTy::data_type* V = state->get<ConstraintRange>(sym)) @@ -323,20 +297,127 @@ RangeConstraintManager::GetRange(const GRState *state, SymbolRef sym) { // AssumeSymX methods: public interface for RangeConstraintManager. //===------------------------------------------------------------------------===/ -#define AssumeX(OP)\ -const GRState*\ -RangeConstraintManager::AssumeSym ## OP(const GRState* state, SymbolRef sym,\ - const llvm::APSInt& V){\ - const RangeSet& R = GetRange(state, sym).Add##OP(state->getBasicVals(), F, V);\ - return !R.isEmpty() ? state->set<ConstraintRange>(sym, R) : NULL;\ +// The syntax for ranges below is mathematical, using [x, y] for closed ranges +// and (x, y) for open ranges. These ranges are modular, corresponding with +// a common treatment of C integer overflow. This means that these methods +// do not have to worry about overflow; RangeSet::Intersect can handle such a +// "wraparound" range. +// As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, +// UINT_MAX, 0, 1, and 2. + +const GRState* +RangeConstraintManager::AssumeSymNE(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment) { + BasicValueFactory &BV = state->getBasicVals(); + + llvm::APSInt Lower = Int-Adjustment; + llvm::APSInt Upper = Lower; + --Lower; + ++Upper; + + // [Int-Adjustment+1, Int-Adjustment-1] + // Notice that the lower bound is greater than the upper bound. + RangeSet New = GetRange(state, sym).Intersect(BV, F, Upper, Lower); + return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); } -AssumeX(EQ) -AssumeX(NE) -AssumeX(LT) -AssumeX(GT) -AssumeX(LE) -AssumeX(GE) +const GRState* +RangeConstraintManager::AssumeSymEQ(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment) { + // [Int-Adjustment, Int-Adjustment] + BasicValueFactory &BV = state->getBasicVals(); + llvm::APSInt AdjInt = Int-Adjustment; + RangeSet New = GetRange(state, sym).Intersect(BV, F, AdjInt, AdjInt); + return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); +} + +const GRState* +RangeConstraintManager::AssumeSymLT(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment) { + BasicValueFactory &BV = state->getBasicVals(); + + QualType T = state->getSymbolManager().getType(sym); + const llvm::APSInt &Min = BV.getMinValue(T); + + // Special case for Int == Min. This is always false. + if (Int == Min) + return NULL; + + llvm::APSInt Lower = Min-Adjustment; + llvm::APSInt Upper = Int-Adjustment; + --Upper; + + RangeSet New = GetRange(state, sym).Intersect(BV, F, Lower, Upper); + return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); +} + +const GRState* +RangeConstraintManager::AssumeSymGT(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment) { + BasicValueFactory &BV = state->getBasicVals(); + + QualType T = state->getSymbolManager().getType(sym); + const llvm::APSInt &Max = BV.getMaxValue(T); + + // Special case for Int == Max. This is always false. + if (Int == Max) + return NULL; + + llvm::APSInt Lower = Int-Adjustment; + llvm::APSInt Upper = Max-Adjustment; + ++Lower; + + RangeSet New = GetRange(state, sym).Intersect(BV, F, Lower, Upper); + return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); +} + +const GRState* +RangeConstraintManager::AssumeSymGE(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment) { + BasicValueFactory &BV = state->getBasicVals(); + + QualType T = state->getSymbolManager().getType(sym); + const llvm::APSInt &Min = BV.getMinValue(T); + + // Special case for Int == Min. This is always feasible. + if (Int == Min) + return state; + + const llvm::APSInt &Max = BV.getMaxValue(T); + + llvm::APSInt Lower = Int-Adjustment; + llvm::APSInt Upper = Max-Adjustment; + + RangeSet New = GetRange(state, sym).Intersect(BV, F, Lower, Upper); + return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); +} + +const GRState* +RangeConstraintManager::AssumeSymLE(const GRState* state, SymbolRef sym, + const llvm::APSInt& Int, + const llvm::APSInt& Adjustment) { + BasicValueFactory &BV = state->getBasicVals(); + + QualType T = state->getSymbolManager().getType(sym); + const llvm::APSInt &Max = BV.getMaxValue(T); + + // Special case for Int == Max. This is always feasible. + if (Int == Max) + return state; + + const llvm::APSInt &Min = BV.getMinValue(T); + + llvm::APSInt Lower = Min-Adjustment; + llvm::APSInt Upper = Int-Adjustment; + + RangeSet New = GetRange(state, sym).Intersect(BV, F, Lower, Upper); + return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); +} //===------------------------------------------------------------------------=== // Pretty-printing. diff --git a/lib/Checker/RegionStore.cpp b/lib/Checker/RegionStore.cpp index c4072fd80307..74a7fee04889 100644 --- a/lib/Checker/RegionStore.cpp +++ b/lib/Checker/RegionStore.cpp @@ -118,22 +118,6 @@ public: } //===----------------------------------------------------------------------===// -// Region "Extents" -//===----------------------------------------------------------------------===// -// -// MemRegions represent chunks of memory with a size (their "extent"). This -// GDM entry tracks the extents for regions. Extents are in bytes. -// -namespace { class RegionExtents {}; } -static int RegionExtentsIndex = 0; -namespace clang { - template<> struct GRStateTrait<RegionExtents> - : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > { - static void* GDMIndex() { return &RegionExtentsIndex; } - }; -} - -//===----------------------------------------------------------------------===// // Utility functions. //===----------------------------------------------------------------------===// @@ -244,14 +228,16 @@ public: Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E, unsigned Count, InvalidatedSymbols *IS) { - return RegionStoreManager::InvalidateRegions(store, &R, &R+1, E, Count, IS); + return RegionStoreManager::InvalidateRegions(store, &R, &R+1, E, Count, IS, + false); } Store InvalidateRegions(Store store, const MemRegion * const *Begin, const MemRegion * const *End, const Expr *E, unsigned Count, - InvalidatedSymbols *IS); + InvalidatedSymbols *IS, + bool invalidateGlobals); public: // Made public for helper classes. @@ -280,6 +266,14 @@ public: // Part of public interface to class. Store Bind(Store store, Loc LV, SVal V); + // BindDefault is only used to initialize a region with a default value. + Store BindDefault(Store store, const MemRegion *R, SVal V) { + RegionBindings B = GetRegionBindings(store); + assert(!Lookup(B, R, BindingKey::Default)); + assert(!Lookup(B, R, BindingKey::Direct)); + return Add(B, R, BindingKey::Default, V).getRoot(); + } + Store BindCompoundLiteral(Store store, const CompoundLiteralExpr* CL, const LocationContext *LC, SVal V); @@ -339,6 +333,12 @@ public: // Part of public interface to class. SVal RetrieveArray(Store store, const TypedRegion* R); + /// Used to lazily generate derived symbols for bindings that are defined + /// implicitly by default bindings in a super region. + Optional<SVal> RetrieveDerivedDefaultValue(RegionBindings B, + const MemRegion *superR, + const TypedRegion *R, QualType Ty); + /// Get the state and region whose binding this region R corresponds to. std::pair<Store, const MemRegion*> GetLazyBinding(RegionBindings B, const MemRegion *R); @@ -352,7 +352,7 @@ public: // Part of public interface to class. /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values. /// It returns a new Store with these values removed. - const GRState *RemoveDeadBindings(GRState &state, Stmt* Loc, + const GRState *RemoveDeadBindings(GRState &state, const StackFrameContext *LCtx, SymbolReaper& SymReaper, llvm::SmallVectorImpl<const MemRegion*>& RegionRoots); @@ -364,18 +364,7 @@ public: // Part of public interface to class. // Region "extents". //===------------------------------------------------------------------===// - const GRState *setExtent(const GRState *state,const MemRegion* R,SVal Extent){ - return state->set<RegionExtents>(R, Extent); - } - - Optional<SVal> getExtent(const GRState *state, const MemRegion *R) { - const SVal *V = state->get<RegionExtents>(R); - if (V) - return *V; - else - return Optional<SVal>(); - } - + // FIXME: This method will soon be eliminated; see the note in Store.h. DefinedOrUnknownSVal getSizeInElements(const GRState *state, const MemRegion* R, QualType EleTy); @@ -391,12 +380,17 @@ public: // Part of public interface to class. const char *sep); void iterBindings(Store store, BindingsHandler& f) { - // FIXME: Implement. - } - - // FIXME: Remove. - BasicValueFactory& getBasicVals() { - return StateMgr.getBasicVals(); + RegionBindings B = GetRegionBindings(store); + for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) { + const BindingKey &K = I.getKey(); + if (!K.isDirect()) + continue; + if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion())) { + // FIXME: Possibly incorporate the offset? + if (!f.HandleBinding(*this, store, R, I.getData())) + return; + } + } } // FIXME: Remove. @@ -483,12 +477,13 @@ public: RegionBindings getRegionBindings() const { return B; } - void AddToCluster(BindingKey K) { + RegionCluster &AddToCluster(BindingKey K) { const MemRegion *R = K.getRegion(); const MemRegion *baseR = R->getBaseRegion(); RegionCluster &C = getCluster(baseR); C.push_back(K, BVC); static_cast<DERIVED*>(this)->VisitAddedToCluster(baseR, C); + return C; } bool isVisited(const MemRegion *R) { @@ -504,15 +499,20 @@ public: return *CRef; } - void GenerateClusters() { + void GenerateClusters(bool includeGlobals = false) { // Scan the entire set of bindings and make the region clusters. for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ - AddToCluster(RI.getKey()); + RegionCluster &C = AddToCluster(RI.getKey()); if (const MemRegion *R = RI.getData().getAsRegion()) { // Generate a cluster, but don't add the region to the cluster // if there aren't any bindings. getCluster(R->getBaseRegion()); } + if (includeGlobals) { + const MemRegion *R = RI.getKey().getRegion(); + if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace())) + AddToWorkList(R, C); + } } } @@ -615,8 +615,8 @@ void InvalidateRegionsWorker::VisitBinding(SVal V) { RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore()); for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ - const MemRegion *baseR = RI.getKey().getRegion(); - if (cast<SubRegion>(baseR)->isSubRegionOf(LazyR)) + const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion()); + if (baseR && baseR->isSubRegionOf(LazyR)) VisitBinding(RI.getData()); } @@ -706,13 +706,14 @@ Store RegionStoreManager::InvalidateRegions(Store store, const MemRegion * const *I, const MemRegion * const *E, const Expr *Ex, unsigned Count, - InvalidatedSymbols *IS) { + InvalidatedSymbols *IS, + bool invalidateGlobals) { InvalidateRegionsWorker W(*this, StateMgr, RegionStoreManager::GetRegionBindings(store), Ex, Count, IS); // Scan the bindings and generate the clusters. - W.GenerateClusters(); + W.GenerateClusters(invalidateGlobals); // Add I .. E to the worklist. for ( ; I != E; ++I) @@ -721,7 +722,20 @@ Store RegionStoreManager::InvalidateRegions(Store store, W.RunWorkList(); // Return the new bindings. - return W.getRegionBindings().getRoot(); + RegionBindings B = W.getRegionBindings(); + + if (invalidateGlobals) { + // Bind the non-static globals memory space to a new symbol that we will + // use to derive the bindings for all non-static globals. + const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(); + SVal V = + ValMgr.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, Ex, + /* symbol type, doesn't matter */ Ctx.IntTy, + Count); + B = Add(B, BindingKey::Make(GS, BindingKey::Default), V); + } + + return B.getRoot(); } //===----------------------------------------------------------------------===// @@ -731,82 +745,19 @@ Store RegionStoreManager::InvalidateRegions(Store store, DefinedOrUnknownSVal RegionStoreManager::getSizeInElements(const GRState *state, const MemRegion *R, QualType EleTy) { + SVal Size = cast<SubRegion>(R)->getExtent(ValMgr); + SValuator &SVator = ValMgr.getSValuator(); + const llvm::APSInt *SizeInt = SVator.getKnownValue(state, Size); + if (!SizeInt) + return UnknownVal(); - switch (R->getKind()) { - case MemRegion::CXXThisRegionKind: - assert(0 && "Cannot get size of 'this' region"); - case MemRegion::GenericMemSpaceRegionKind: - case MemRegion::StackLocalsSpaceRegionKind: - case MemRegion::StackArgumentsSpaceRegionKind: - case MemRegion::HeapSpaceRegionKind: - case MemRegion::GlobalsSpaceRegionKind: - case MemRegion::UnknownSpaceRegionKind: - assert(0 && "Cannot index into a MemSpace"); - return UnknownVal(); - - case MemRegion::FunctionTextRegionKind: - case MemRegion::BlockTextRegionKind: - case MemRegion::BlockDataRegionKind: - // Technically this can happen if people do funny things with casts. - return UnknownVal(); - - // Not yet handled. - case MemRegion::AllocaRegionKind: - case MemRegion::CompoundLiteralRegionKind: - case MemRegion::ElementRegionKind: - case MemRegion::FieldRegionKind: - case MemRegion::ObjCIvarRegionKind: - case MemRegion::CXXObjectRegionKind: - return UnknownVal(); - - case MemRegion::SymbolicRegionKind: { - const SVal *Size = state->get<RegionExtents>(R); - if (!Size) - return UnknownVal(); - const nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(Size); - if (!CI) - return UnknownVal(); - - CharUnits RegionSize = - CharUnits::fromQuantity(CI->getValue().getSExtValue()); - CharUnits EleSize = getContext().getTypeSizeInChars(EleTy); - assert(RegionSize % EleSize == 0); - - return ValMgr.makeIntVal(RegionSize / EleSize, false); - } - - case MemRegion::StringRegionKind: { - const StringLiteral* Str = cast<StringRegion>(R)->getStringLiteral(); - // We intentionally made the size value signed because it participates in - // operations with signed indices. - return ValMgr.makeIntVal(Str->getByteLength()+1, false); - } - - case MemRegion::VarRegionKind: { - const VarRegion* VR = cast<VarRegion>(R); - // Get the type of the variable. - QualType T = VR->getDesugaredValueType(getContext()); - - // FIXME: Handle variable-length arrays. - if (isa<VariableArrayType>(T)) - return UnknownVal(); - - if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) { - // return the size as signed integer. - return ValMgr.makeIntVal(CAT->getSize(), false); - } - - // Clients can reinterpret ordinary variables as arrays, possibly of - // another type. The width is rounded down to ensure that an access is - // entirely within bounds. - CharUnits VarSize = getContext().getTypeSizeInChars(T); - CharUnits EleSize = getContext().getTypeSizeInChars(EleTy); - return ValMgr.makeIntVal(VarSize / EleSize, false); - } - } + CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue()); + CharUnits EleSize = getContext().getTypeSizeInChars(EleTy); - assert(0 && "Unreachable"); - return UnknownVal(); + // If a variable is reinterpreted as a type that doesn't fit into a larger + // type evenly, round it down. + // This is a signed value, since it's used in arithmetic with signed indices. + return ValMgr.makeIntVal(RegionSize / EleSize, false); } //===----------------------------------------------------------------------===// @@ -849,6 +800,19 @@ SVal RegionStoreManager::EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R, if (!isa<loc::MemRegionVal>(L)) return UnknownVal(); + // Special case for zero RHS. + if (R.isZeroConstant()) { + switch (Op) { + default: + // Handle it normally. + break; + case BinaryOperator::Add: + case BinaryOperator::Sub: + // FIXME: does this need to be casted to match resultTy? + return L; + } + } + const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion(); const ElementRegion *ER = 0; @@ -870,8 +834,7 @@ SVal RegionStoreManager::EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R, } case MemRegion::AllocaRegionKind: { const AllocaRegion *AR = cast<AllocaRegion>(MR); - QualType T = getContext().CharTy; // Create an ElementRegion of bytes. - QualType EleTy = T->getAs<PointerType>()->getPointeeType(); + QualType EleTy = getContext().CharTy; // Create an ElementRegion of bytes. SVal ZeroIdx = ValMgr.makeZeroArrayIndex(); ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, getContext()); break; @@ -907,7 +870,8 @@ SVal RegionStoreManager::EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R, case MemRegion::StackLocalsSpaceRegionKind: case MemRegion::StackArgumentsSpaceRegionKind: case MemRegion::HeapSpaceRegionKind: - case MemRegion::GlobalsSpaceRegionKind: + case MemRegion::NonStaticGlobalSpaceRegionKind: + case MemRegion::StaticGlobalSpaceRegionKind: case MemRegion::UnknownSpaceRegionKind: assert(0 && "Cannot perform pointer arithmetic on a MemSpace"); return UnknownVal(); @@ -946,7 +910,8 @@ SVal RegionStoreManager::EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R, //===----------------------------------------------------------------------===// Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B, - const MemRegion *R) { + const MemRegion *R) { + if (const SVal *V = Lookup(B, R, BindingKey::Direct)) return *V; @@ -1009,8 +974,13 @@ SVal RegionStoreManager::Retrieve(Store store, Loc L, QualType T) { const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion(); - if (isa<AllocaRegion>(MR) || isa<SymbolicRegion>(MR)) + if (isa<AllocaRegion>(MR) || isa<SymbolicRegion>(MR)) { + if (T.isNull()) { + const SymbolicRegion *SR = cast<SymbolicRegion>(MR); + T = SR->getSymbol()->getType(getContext()); + } MR = GetElementZeroRegion(MR, T); + } if (isa<CodeTextRegion>(MR)) { assert(0 && "Why load from a code text region?"); @@ -1172,27 +1142,33 @@ SVal RegionStoreManager::RetrieveElement(Store store, } } - // Check if the immediate super region has a direct binding. - if (const Optional<SVal> &V = getDirectBinding(B, superR)) { - if (SymbolRef parentSym = V->getAsSymbol()) - return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R); - - if (V->isUnknownOrUndef()) - return *V; - - // Handle LazyCompoundVals for the immediate super region. Other cases - // are handled in 'RetrieveFieldOrElementCommon'. - if (const nonloc::LazyCompoundVal *LCV = - dyn_cast<nonloc::LazyCompoundVal>(V)) { - - R = MRMgr.getElementRegionWithSuper(R, LCV->getRegion()); - return RetrieveElement(LCV->getStore(), R); + // Handle the case where we are indexing into a larger scalar object. + // For example, this handles: + // int x = ... + // char *y = &x; + // return *y; + // FIXME: This is a hack, and doesn't do anything really intelligent yet. + const RegionRawOffset &O = R->getAsRawOffset(); + if (const TypedRegion *baseR = dyn_cast_or_null<TypedRegion>(O.getRegion())) { + QualType baseT = baseR->getValueType(Ctx); + if (baseT->isScalarType()) { + QualType elemT = R->getElementType(); + if (elemT->isScalarType()) { + if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) { + if (const Optional<SVal> &V = getDirectBinding(B, superR)) { + if (SymbolRef parentSym = V->getAsSymbol()) + return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R); + + if (V->isUnknownOrUndef()) + return *V; + // Other cases: give up. We are indexing into a larger object + // that has some value, but we don't know how to handle that yet. + return UnknownVal(); + } + } + } } - - // Other cases: give up. - return UnknownVal(); } - return RetrieveFieldOrElementCommon(store, R, R->getElementType(), superR); } @@ -1208,6 +1184,28 @@ SVal RegionStoreManager::RetrieveField(Store store, return RetrieveFieldOrElementCommon(store, R, Ty, R->getSuperRegion()); } +Optional<SVal> +RegionStoreManager::RetrieveDerivedDefaultValue(RegionBindings B, + const MemRegion *superR, + const TypedRegion *R, + QualType Ty) { + + if (const Optional<SVal> &D = getDefaultBinding(B, superR)) { + if (SymbolRef parentSym = D->getAsSymbol()) + return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R); + + if (D->isZeroConstant()) + return ValMgr.makeZeroVal(Ty); + + if (D->isUnknownOrUndef()) + return *D; + + assert(0 && "Unknown default value"); + } + + return Optional<SVal>(); +} + SVal RegionStoreManager::RetrieveFieldOrElementCommon(Store store, const TypedRegion *R, QualType Ty, @@ -1219,18 +1217,8 @@ SVal RegionStoreManager::RetrieveFieldOrElementCommon(Store store, RegionBindings B = GetRegionBindings(store); while (superR) { - if (const Optional<SVal> &D = getDefaultBinding(B, superR)) { - if (SymbolRef parentSym = D->getAsSymbol()) - return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R); - - if (D->isZeroConstant()) - return ValMgr.makeZeroVal(Ty); - - if (D->isUnknown()) - return *D; - - assert(0 && "Unknown default value"); - } + if (const Optional<SVal> &D = RetrieveDerivedDefaultValue(B, superR, R, Ty)) + return *D; // If our super region is a field or element itself, walk up the region // hierarchy to see if there is a default value installed in an ancestor. @@ -1311,7 +1299,7 @@ SVal RegionStoreManager::RetrieveVar(Store store, const VarRegion *R) { return ValMgr.getRegionValueSymbolVal(R); if (isa<GlobalsSpaceRegion>(MS)) { - if (VD->isFileVarDecl()) { + if (isa<NonStaticGlobalSpaceRegion>(MS)) { // Is 'VD' declared constant? If so, retrieve the constant value. QualType CT = Ctx.getCanonicalType(T); if (CT.isConstQualified()) { @@ -1326,6 +1314,9 @@ SVal RegionStoreManager::RetrieveVar(Store store, const VarRegion *R) { } } + if (const Optional<SVal> &V = RetrieveDerivedDefaultValue(B, MS, R, CT)) + return V.getValue(); + return ValMgr.getRegionValueSymbolVal(R); } @@ -1449,6 +1440,7 @@ Store RegionStoreManager::BindCompoundLiteral(Store store, V); } + Store RegionStoreManager::setImplicitDefaultValue(Store store, const MemRegion *R, QualType T) { @@ -1691,15 +1683,14 @@ class RemoveDeadBindingsWorker : public ClusterAnalysis<RemoveDeadBindingsWorker> { llvm::SmallVector<const SymbolicRegion*, 12> Postponed; SymbolReaper &SymReaper; - Stmt *Loc; const StackFrameContext *CurrentLCtx; - + public: RemoveDeadBindingsWorker(RegionStoreManager &rm, GRStateManager &stateMgr, RegionBindings b, SymbolReaper &symReaper, - Stmt *loc, const StackFrameContext *LCtx) + const StackFrameContext *LCtx) : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr, b), - SymReaper(symReaper), Loc(loc), CurrentLCtx(LCtx) {} + SymReaper(symReaper), CurrentLCtx(LCtx) {} // Called by ClusterAnalysis. void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C); @@ -1715,7 +1706,7 @@ void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C) { if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { - if (SymReaper.isLive(Loc, VR)) + if (SymReaper.isLive(VR)) AddToWorkList(baseR, C); return; @@ -1730,9 +1721,14 @@ void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, return; } + if (isa<NonStaticGlobalSpaceRegion>(baseR)) { + AddToWorkList(baseR, C); + return; + } + // CXXThisRegion in the current or parent location context is live. if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { - const StackArgumentsSpaceRegion *StackReg = + const StackArgumentsSpaceRegion *StackReg = cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); const StackFrameContext *RegCtx = StackReg->getStackFrame(); if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)) @@ -1754,8 +1750,8 @@ void RemoveDeadBindingsWorker::VisitBinding(SVal V) { const MemRegion *LazyR = LCS->getRegion(); RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore()); for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ - const MemRegion *baseR = RI.getKey().getRegion(); - if (cast<SubRegion>(baseR)->isSubRegionOf(LazyR)) + const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion()); + if (baseR && baseR->isSubRegionOf(LazyR)) VisitBinding(RI.getData()); } return; @@ -1822,13 +1818,13 @@ bool RemoveDeadBindingsWorker::UpdatePostponed() { return changed; } -const GRState *RegionStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc, +const GRState *RegionStoreManager::RemoveDeadBindings(GRState &state, const StackFrameContext *LCtx, SymbolReaper& SymReaper, llvm::SmallVectorImpl<const MemRegion*>& RegionRoots) { RegionBindings B = GetRegionBindings(state.getStore()); - RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, Loc, LCtx); + RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); W.GenerateClusters(); // Enqueue the region roots onto the worklist. @@ -1862,13 +1858,6 @@ const GRState *RegionStoreManager::RemoveDeadBindings(GRState &state, Stmt* Loc, } state.setStore(B.getRoot()); const GRState *s = StateMgr.getPersistentState(state); - // Remove the extents of dead symbolic regions. - llvm::ImmutableMap<const MemRegion*,SVal> Extents = s->get<RegionExtents>(); - for (llvm::ImmutableMap<const MemRegion *, SVal>::iterator I=Extents.begin(), - E = Extents.end(); I != E; ++I) { - if (!W.isVisited(I->first)) - s = s->remove<RegionExtents>(I->first); - } return s; } @@ -1887,9 +1876,9 @@ GRState const *RegionStoreManager::EnterStackFrame(GRState const *state, SVal ArgVal = state->getSVal(*AI); store = Bind(store, ValMgr.makeLoc(MRMgr.getVarRegion(*PI,frame)),ArgVal); } - } else if (const CXXConstructExpr *CE = + } else if (const CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(frame->getCallSite())) { - CXXConstructExpr::const_arg_iterator AI = CE->arg_begin(), + CXXConstructExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end(); // Copy the arg expression value to the arg variables. diff --git a/lib/Checker/ReturnStackAddressChecker.cpp b/lib/Checker/ReturnStackAddressChecker.cpp deleted file mode 100644 index 35b1cdebf620..000000000000 --- a/lib/Checker/ReturnStackAddressChecker.cpp +++ /dev/null @@ -1,125 +0,0 @@ -//== ReturnStackAddressChecker.cpp ------------------------------*- C++ -*--==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines ReturnStackAddressChecker, which is a path-sensitive -// check which looks for the addresses of stack variables being returned to -// callers. -// -//===----------------------------------------------------------------------===// - -#include "GRExprEngineInternalChecks.h" -#include "clang/Checker/BugReporter/BugType.h" -#include "clang/Checker/PathSensitive/GRExprEngine.h" -#include "clang/Checker/PathSensitive/CheckerVisitor.h" -#include "clang/Basic/SourceManager.h" -#include "llvm/ADT/SmallString.h" - -using namespace clang; - -namespace { -class ReturnStackAddressChecker : - public CheckerVisitor<ReturnStackAddressChecker> { - BuiltinBug *BT; -public: - ReturnStackAddressChecker() : BT(0) {} - static void *getTag(); - void PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *RS); -private: - void EmitStackError(CheckerContext &C, const MemRegion *R, const Expr *RetE); -}; -} - -void clang::RegisterReturnStackAddressChecker(GRExprEngine &Eng) { - Eng.registerCheck(new ReturnStackAddressChecker()); -} - -void *ReturnStackAddressChecker::getTag() { - static int x = 0; return &x; -} - -void ReturnStackAddressChecker::EmitStackError(CheckerContext &C, - const MemRegion *R, - const Expr *RetE) { - ExplodedNode *N = C.GenerateSink(); - - if (!N) - return; - - if (!BT) - BT = new BuiltinBug("Return of address to stack-allocated memory"); - - // Generate a report for this bug. - llvm::SmallString<512> buf; - llvm::raw_svector_ostream os(buf); - SourceRange range; - - // Get the base region, stripping away fields and elements. - R = R->getBaseRegion(); - - // Check if the region is a compound literal. - if (const CompoundLiteralRegion* CR = dyn_cast<CompoundLiteralRegion>(R)) { - const CompoundLiteralExpr* CL = CR->getLiteralExpr(); - os << "Address of stack memory associated with a compound literal " - "declared on line " - << C.getSourceManager().getInstantiationLineNumber(CL->getLocStart()) - << " returned to caller"; - range = CL->getSourceRange(); - } - else if (const AllocaRegion* AR = dyn_cast<AllocaRegion>(R)) { - const Expr* ARE = AR->getExpr(); - SourceLocation L = ARE->getLocStart(); - range = ARE->getSourceRange(); - os << "Address of stack memory allocated by call to alloca() on line " - << C.getSourceManager().getInstantiationLineNumber(L) - << " returned to caller"; - } - else if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { - const BlockDecl *BD = BR->getCodeRegion()->getDecl(); - SourceLocation L = BD->getLocStart(); - range = BD->getSourceRange(); - os << "Address of stack-allocated block declared on line " - << C.getSourceManager().getInstantiationLineNumber(L) - << " returned to caller"; - } - else if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { - os << "Address of stack memory associated with local variable '" - << VR->getString() << "' returned"; - range = VR->getDecl()->getSourceRange(); - } - else { - assert(false && "Invalid region in ReturnStackAddressChecker."); - return; - } - - RangedBugReport *report = new RangedBugReport(*BT, os.str(), N); - report->addRange(RetE->getSourceRange()); - if (range.isValid()) - report->addRange(range); - - C.EmitReport(report); -} - -void ReturnStackAddressChecker::PreVisitReturnStmt(CheckerContext &C, - const ReturnStmt *RS) { - - const Expr *RetE = RS->getRetValue(); - if (!RetE) - return; - - SVal V = C.getState()->getSVal(RetE); - const MemRegion *R = V.getAsRegion(); - - if (!R || !R->hasStackStorage()) - return; - - if (R->hasStackStorage()) { - EmitStackError(C, R, RetE); - return; - } -} diff --git a/lib/Checker/SVals.cpp b/lib/Checker/SVals.cpp index d756be70dc25..7a99e8681df9 100644 --- a/lib/Checker/SVals.cpp +++ b/lib/Checker/SVals.cpp @@ -200,15 +200,19 @@ bool SVal::isConstant() const { return isa<nonloc::ConcreteInt>(this) || isa<loc::ConcreteInt>(this); } -bool SVal::isZeroConstant() const { +bool SVal::isConstant(int I) const { if (isa<loc::ConcreteInt>(*this)) - return cast<loc::ConcreteInt>(*this).getValue() == 0; + return cast<loc::ConcreteInt>(*this).getValue() == I; else if (isa<nonloc::ConcreteInt>(*this)) - return cast<nonloc::ConcreteInt>(*this).getValue() == 0; + return cast<nonloc::ConcreteInt>(*this).getValue() == I; else return false; } +bool SVal::isZeroConstant() const { + return isConstant(0); +} + //===----------------------------------------------------------------------===// // Transfer function dispatch for Non-Locs. diff --git a/lib/Checker/SValuator.cpp b/lib/Checker/SValuator.cpp index 542fc1b1078d..a7e15fc3fd73 100644 --- a/lib/Checker/SValuator.cpp +++ b/lib/Checker/SValuator.cpp @@ -29,15 +29,15 @@ SVal SValuator::EvalBinOp(const GRState *ST, BinaryOperator::Opcode Op, if (isa<Loc>(L)) { if (isa<Loc>(R)) - return EvalBinOpLL(Op, cast<Loc>(L), cast<Loc>(R), T); + return EvalBinOpLL(ST, Op, cast<Loc>(L), cast<Loc>(R), T); return EvalBinOpLN(ST, Op, cast<Loc>(L), cast<NonLoc>(R), T); } if (isa<Loc>(R)) { - // Support pointer arithmetic where the increment/decrement operand - // is on the left and the pointer on the right. - assert(Op == BinaryOperator::Add || Op == BinaryOperator::Sub); + // Support pointer arithmetic where the addend is on the left + // and the pointer on the right. + assert(Op == BinaryOperator::Add); // Commute the operands. return EvalBinOpLN(ST, Op, cast<Loc>(R), cast<NonLoc>(L), T); diff --git a/lib/Checker/SimpleConstraintManager.cpp b/lib/Checker/SimpleConstraintManager.cpp index 8c423a99777d..321381b045ad 100644 --- a/lib/Checker/SimpleConstraintManager.cpp +++ b/lib/Checker/SimpleConstraintManager.cpp @@ -35,12 +35,11 @@ bool SimpleConstraintManager::canReasonAbout(SVal X) const { case BinaryOperator::Or: case BinaryOperator::Xor: return false; - // We don't reason yet about arithmetic constraints on symbolic values. + // We don't reason yet about these arithmetic constraints on + // symbolic values. case BinaryOperator::Mul: case BinaryOperator::Div: case BinaryOperator::Rem: - case BinaryOperator::Add: - case BinaryOperator::Sub: case BinaryOperator::Shl: case BinaryOperator::Shr: return false; @@ -90,12 +89,11 @@ const GRState *SimpleConstraintManager::AssumeAux(const GRState *state, while (SubR) { // FIXME: now we only find the first symbolic region. if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SubR)) { + const llvm::APSInt &zero = BasicVals.getZeroWithPtrWidth(); if (Assumption) - return AssumeSymNE(state, SymR->getSymbol(), - BasicVals.getZeroWithPtrWidth()); + return AssumeSymNE(state, SymR->getSymbol(), zero, zero); else - return AssumeSymEQ(state, SymR->getSymbol(), - BasicVals.getZeroWithPtrWidth()); + return AssumeSymEQ(state, SymR->getSymbol(), zero, zero); } SubR = dyn_cast<SubRegion>(SubR->getSuperRegion()); } @@ -121,11 +119,27 @@ const GRState *SimpleConstraintManager::Assume(const GRState *state, return SU.ProcessAssume(state, cond, assumption); } +static BinaryOperator::Opcode NegateComparison(BinaryOperator::Opcode op) { + // FIXME: This should probably be part of BinaryOperator, since this isn't + // the only place it's used. (This code was copied from SimpleSValuator.cpp.) + switch (op) { + default: + assert(false && "Invalid opcode."); + case BinaryOperator::LT: return BinaryOperator::GE; + case BinaryOperator::GT: return BinaryOperator::LE; + case BinaryOperator::LE: return BinaryOperator::GT; + case BinaryOperator::GE: return BinaryOperator::LT; + case BinaryOperator::EQ: return BinaryOperator::NE; + case BinaryOperator::NE: return BinaryOperator::EQ; + } +} + const GRState *SimpleConstraintManager::AssumeAux(const GRState *state, NonLoc Cond, bool Assumption) { - // We cannot reason about SymIntExpr and SymSymExpr. + // We cannot reason about SymSymExprs, + // and can only reason about some SymIntExprs. if (!canReasonAbout(Cond)) { // Just return the current state indicating that the path is feasible. // This may be an over-approximation of what is possible. @@ -144,30 +158,35 @@ const GRState *SimpleConstraintManager::AssumeAux(const GRState *state, SymbolRef sym = SV.getSymbol(); QualType T = SymMgr.getType(sym); const llvm::APSInt &zero = BasicVals.getValue(0, T); - - return Assumption ? AssumeSymNE(state, sym, zero) - : AssumeSymEQ(state, sym, zero); + if (Assumption) + return AssumeSymNE(state, sym, zero, zero); + else + return AssumeSymEQ(state, sym, zero, zero); } case nonloc::SymExprValKind: { nonloc::SymExprVal V = cast<nonloc::SymExprVal>(Cond); - if (const SymIntExpr *SE = dyn_cast<SymIntExpr>(V.getSymbolicExpression())){ - // FIXME: This is a hack. It silently converts the RHS integer to be - // of the same type as on the left side. This should be removed once - // we support truncation/extension of symbolic values. - GRStateManager &StateMgr = state->getStateManager(); - ASTContext &Ctx = StateMgr.getContext(); - QualType LHSType = SE->getLHS()->getType(Ctx); - BasicValueFactory &BasicVals = StateMgr.getBasicVals(); - const llvm::APSInt &RHS = BasicVals.Convert(LHSType, SE->getRHS()); - SymIntExpr SENew(SE->getLHS(), SE->getOpcode(), RHS, SE->getType(Ctx)); - - return AssumeSymInt(state, Assumption, &SENew); + + // For now, we only handle expressions whose RHS is an integer. + // All other expressions are assumed to be feasible. + const SymIntExpr *SE = dyn_cast<SymIntExpr>(V.getSymbolicExpression()); + if (!SE) + return state; + + BinaryOperator::Opcode op = SE->getOpcode(); + // Implicitly compare non-comparison expressions to 0. + if (!BinaryOperator::isComparisonOp(op)) { + QualType T = SymMgr.getType(SE); + const llvm::APSInt &zero = BasicVals.getValue(0, T); + op = (Assumption ? BinaryOperator::NE : BinaryOperator::EQ); + return AssumeSymRel(state, SE, op, zero); } - // For all other symbolic expressions, over-approximate and consider - // the constraint feasible. - return state; + // From here on out, op is the real comparison we'll be testing. + if (!Assumption) + op = NegateComparison(op); + + return AssumeSymRel(state, SE->getLHS(), op, SE->getRHS()); } case nonloc::ConcreteIntKind: { @@ -182,43 +201,98 @@ const GRState *SimpleConstraintManager::AssumeAux(const GRState *state, } // end switch } -const GRState *SimpleConstraintManager::AssumeSymInt(const GRState *state, - bool Assumption, - const SymIntExpr *SE) { +const GRState *SimpleConstraintManager::AssumeSymRel(const GRState *state, + const SymExpr *LHS, + BinaryOperator::Opcode op, + const llvm::APSInt& Int) { + assert(BinaryOperator::isComparisonOp(op) && + "Non-comparison ops should be rewritten as comparisons to zero."); + + // We only handle simple comparisons of the form "$sym == constant" + // or "($sym+constant1) == constant2". + // The adjustment is "constant1" in the above expression. It's used to + // "slide" the solution range around for modular arithmetic. For example, + // x < 4 has the solution [0, 3]. x+2 < 4 has the solution [0-2, 3-2], which + // in modular arithmetic is [0, 1] U [UINT_MAX-1, UINT_MAX]. It's up to + // the subclasses of SimpleConstraintManager to handle the adjustment. + llvm::APSInt Adjustment; + + // First check if the LHS is a simple symbol reference. + SymbolRef Sym = dyn_cast<SymbolData>(LHS); + if (Sym) { + Adjustment = 0; + } else { + // Next, see if it's a "($sym+constant1)" expression. + const SymIntExpr *SE = dyn_cast<SymIntExpr>(LHS); + + // We don't handle "($sym1+$sym2)". + // Give up and assume the constraint is feasible. + if (!SE) + return state; + + // We don't handle "(<expr>+constant1)". + // Give up and assume the constraint is feasible. + Sym = dyn_cast<SymbolData>(SE->getLHS()); + if (!Sym) + return state; + + // Get the constant out of the expression "($sym+constant1)". + switch (SE->getOpcode()) { + case BinaryOperator::Add: + Adjustment = SE->getRHS(); + break; + case BinaryOperator::Sub: + Adjustment = -SE->getRHS(); + break; + default: + // We don't handle non-additive operators. + // Give up and assume the constraint is feasible. + return state; + } + } + + // FIXME: This next section is a hack. It silently converts the integers to + // be of the same type as the symbol, which is not always correct. Really the + // comparisons should be performed using the Int's type, then mapped back to + // the symbol's range of values. + GRStateManager &StateMgr = state->getStateManager(); + ASTContext &Ctx = StateMgr.getContext(); + + QualType T = Sym->getType(Ctx); + assert(T->isIntegerType() || Loc::IsLocType(T)); + unsigned bitwidth = Ctx.getTypeSize(T); + bool isSymUnsigned = T->isUnsignedIntegerType() || Loc::IsLocType(T); + // Convert the adjustment. + Adjustment.setIsUnsigned(isSymUnsigned); + Adjustment.extOrTrunc(bitwidth); - // Here we assume that LHS is a symbol. This is consistent with the - // rest of the constraint manager logic. - SymbolRef Sym = cast<SymbolData>(SE->getLHS()); - const llvm::APSInt &Int = SE->getRHS(); + // Convert the right-hand side integer. + llvm::APSInt ConvertedInt(Int, isSymUnsigned); + ConvertedInt.extOrTrunc(bitwidth); - switch (SE->getOpcode()) { + switch (op) { default: // No logic yet for other operators. Assume the constraint is feasible. return state; case BinaryOperator::EQ: - return Assumption ? AssumeSymEQ(state, Sym, Int) - : AssumeSymNE(state, Sym, Int); + return AssumeSymEQ(state, Sym, ConvertedInt, Adjustment); case BinaryOperator::NE: - return Assumption ? AssumeSymNE(state, Sym, Int) - : AssumeSymEQ(state, Sym, Int); + return AssumeSymNE(state, Sym, ConvertedInt, Adjustment); + case BinaryOperator::GT: - return Assumption ? AssumeSymGT(state, Sym, Int) - : AssumeSymLE(state, Sym, Int); + return AssumeSymGT(state, Sym, ConvertedInt, Adjustment); case BinaryOperator::GE: - return Assumption ? AssumeSymGE(state, Sym, Int) - : AssumeSymLT(state, Sym, Int); + return AssumeSymGE(state, Sym, ConvertedInt, Adjustment); case BinaryOperator::LT: - return Assumption ? AssumeSymLT(state, Sym, Int) - : AssumeSymGE(state, Sym, Int); + return AssumeSymLT(state, Sym, ConvertedInt, Adjustment); case BinaryOperator::LE: - return Assumption ? AssumeSymLE(state, Sym, Int) - : AssumeSymGT(state, Sym, Int); + return AssumeSymLE(state, Sym, ConvertedInt, Adjustment); } // end switch } diff --git a/lib/Checker/SimpleConstraintManager.h b/lib/Checker/SimpleConstraintManager.h index 5f20e0072b20..45057e64f31f 100644 --- a/lib/Checker/SimpleConstraintManager.h +++ b/lib/Checker/SimpleConstraintManager.h @@ -38,8 +38,10 @@ public: const GRState *Assume(const GRState *state, NonLoc Cond, bool Assumption); - const GRState *AssumeSymInt(const GRState *state, bool Assumption, - const SymIntExpr *SE); + const GRState *AssumeSymRel(const GRState *state, + const SymExpr *LHS, + BinaryOperator::Opcode op, + const llvm::APSInt& Int); const GRState *AssumeInBound(const GRState *state, DefinedSVal Idx, DefinedSVal UpperBound, @@ -51,23 +53,31 @@ protected: // Interface that subclasses must implement. //===------------------------------------------------------------------===// + // Each of these is of the form "$sym+Adj <> V", where "<>" is the comparison + // operation for the method being invoked. virtual const GRState *AssumeSymNE(const GRState *state, SymbolRef sym, - const llvm::APSInt& V) = 0; + const llvm::APSInt& V, + const llvm::APSInt& Adjustment) = 0; virtual const GRState *AssumeSymEQ(const GRState *state, SymbolRef sym, - const llvm::APSInt& V) = 0; + const llvm::APSInt& V, + const llvm::APSInt& Adjustment) = 0; virtual const GRState *AssumeSymLT(const GRState *state, SymbolRef sym, - const llvm::APSInt& V) = 0; + const llvm::APSInt& V, + const llvm::APSInt& Adjustment) = 0; virtual const GRState *AssumeSymGT(const GRState *state, SymbolRef sym, - const llvm::APSInt& V) = 0; + const llvm::APSInt& V, + const llvm::APSInt& Adjustment) = 0; virtual const GRState *AssumeSymLE(const GRState *state, SymbolRef sym, - const llvm::APSInt& V) = 0; + const llvm::APSInt& V, + const llvm::APSInt& Adjustment) = 0; virtual const GRState *AssumeSymGE(const GRState *state, SymbolRef sym, - const llvm::APSInt& V) = 0; + const llvm::APSInt& V, + const llvm::APSInt& Adjustment) = 0; //===------------------------------------------------------------------===// // Internal implementation. diff --git a/lib/Checker/SimpleSValuator.cpp b/lib/Checker/SimpleSValuator.cpp index dd38a435a1d7..3bc4ee7d0613 100644 --- a/lib/Checker/SimpleSValuator.cpp +++ b/lib/Checker/SimpleSValuator.cpp @@ -30,10 +30,17 @@ public: virtual SVal EvalComplement(NonLoc val); virtual SVal EvalBinOpNN(const GRState *state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy); - virtual SVal EvalBinOpLL(BinaryOperator::Opcode op, Loc lhs, Loc rhs, - QualType resultTy); + virtual SVal EvalBinOpLL(const GRState *state, BinaryOperator::Opcode op, + Loc lhs, Loc rhs, QualType resultTy); virtual SVal EvalBinOpLN(const GRState *state, BinaryOperator::Opcode op, Loc lhs, NonLoc rhs, QualType resultTy); + + /// getKnownValue - Evaluates a given SVal. If the SVal has only one possible + /// (integer) value, that value is returned. Otherwise, returns NULL. + virtual const llvm::APSInt *getKnownValue(const GRState *state, SVal V); + + SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op, + const llvm::APSInt &RHS, QualType resultTy); }; } // end anonymous namespace @@ -170,45 +177,93 @@ static BinaryOperator::Opcode NegateComparison(BinaryOperator::Opcode op) { } } -// Equality operators for Locs. -// FIXME: All this logic will be revamped when we have MemRegion::getLocation() -// implemented. - -static SVal EvalEquality(ValueManager &ValMgr, Loc lhs, Loc rhs, bool isEqual, - QualType resultTy) { +static BinaryOperator::Opcode ReverseComparison(BinaryOperator::Opcode op) { + switch (op) { + default: + assert(false && "Invalid opcode."); + case BinaryOperator::LT: return BinaryOperator::GT; + case BinaryOperator::GT: return BinaryOperator::LT; + case BinaryOperator::LE: return BinaryOperator::GE; + case BinaryOperator::GE: return BinaryOperator::LE; + case BinaryOperator::EQ: + case BinaryOperator::NE: + return op; + } +} - switch (lhs.getSubKind()) { - default: - assert(false && "EQ/NE not implemented for this Loc."); - return UnknownVal(); +SVal SimpleSValuator::MakeSymIntVal(const SymExpr *LHS, + BinaryOperator::Opcode op, + const llvm::APSInt &RHS, + QualType resultTy) { + bool isIdempotent = false; - case loc::ConcreteIntKind: { - if (SymbolRef rSym = rhs.getAsSymbol()) - return ValMgr.makeNonLoc(rSym, - isEqual ? BinaryOperator::EQ - : BinaryOperator::NE, - cast<loc::ConcreteInt>(lhs).getValue(), - resultTy); - break; - } - case loc::MemRegionKind: { - if (SymbolRef lSym = lhs.getAsLocSymbol()) { - if (isa<loc::ConcreteInt>(rhs)) { - return ValMgr.makeNonLoc(lSym, - isEqual ? BinaryOperator::EQ - : BinaryOperator::NE, - cast<loc::ConcreteInt>(rhs).getValue(), - resultTy); - } - } - break; + // Check for a few special cases with known reductions first. + switch (op) { + default: + // We can't reduce this case; just treat it normally. + break; + case BinaryOperator::Mul: + // a*0 and a*1 + if (RHS == 0) + return ValMgr.makeIntVal(0, resultTy); + else if (RHS == 1) + isIdempotent = true; + break; + case BinaryOperator::Div: + // a/0 and a/1 + if (RHS == 0) + // This is also handled elsewhere. + return UndefinedVal(); + else if (RHS == 1) + isIdempotent = true; + break; + case BinaryOperator::Rem: + // a%0 and a%1 + if (RHS == 0) + // This is also handled elsewhere. + return UndefinedVal(); + else if (RHS == 1) + return ValMgr.makeIntVal(0, resultTy); + break; + case BinaryOperator::Add: + case BinaryOperator::Sub: + case BinaryOperator::Shl: + case BinaryOperator::Shr: + case BinaryOperator::Xor: + // a+0, a-0, a<<0, a>>0, a^0 + if (RHS == 0) + isIdempotent = true; + break; + case BinaryOperator::And: + // a&0 and a&(~0) + if (RHS == 0) + return ValMgr.makeIntVal(0, resultTy); + else if (RHS.isAllOnesValue()) + isIdempotent = true; + break; + case BinaryOperator::Or: + // a|0 and a|(~0) + if (RHS == 0) + isIdempotent = true; + else if (RHS.isAllOnesValue()) { + BasicValueFactory &BVF = ValMgr.getBasicValueFactory(); + const llvm::APSInt &Result = BVF.Convert(resultTy, RHS); + return nonloc::ConcreteInt(Result); } + break; + } - case loc::GotoLabelKind: - break; + // Idempotent ops (like a*1) can still change the type of an expression. + // Wrap the LHS up in a NonLoc again and let EvalCastNL do the dirty work. + if (isIdempotent) { + if (SymbolRef LHSSym = dyn_cast<SymbolData>(LHS)) + return EvalCastNL(nonloc::SymbolVal(LHSSym), resultTy); + return EvalCastNL(nonloc::SymExprVal(LHS), resultTy); } - return ValMgr.makeTruthVal(isEqual ? lhs == rhs : lhs != rhs, resultTy); + // If we reach this point, the expression cannot be simplified. + // Make a SymExprVal for the entire thing. + return ValMgr.makeNonLoc(LHS, op, RHS, resultTy); } SVal SimpleSValuator::EvalBinOpNN(const GRState *state, @@ -228,6 +283,12 @@ SVal SimpleSValuator::EvalBinOpNN(const GRState *state, case BinaryOperator::GT: case BinaryOperator::NE: return ValMgr.makeTruthVal(false, resultTy); + case BinaryOperator::Xor: + case BinaryOperator::Sub: + return ValMgr.makeIntVal(0, resultTy); + case BinaryOperator::Or: + case BinaryOperator::And: + return EvalCastNL(lhs, resultTy); } while (1) { @@ -238,7 +299,8 @@ SVal SimpleSValuator::EvalBinOpNN(const GRState *state, Loc lhsL = cast<nonloc::LocAsInteger>(lhs).getLoc(); switch (rhs.getSubKind()) { case nonloc::LocAsIntegerKind: - return EvalBinOpLL(op, lhsL, cast<nonloc::LocAsInteger>(rhs).getLoc(), + return EvalBinOpLL(state, op, lhsL, + cast<nonloc::LocAsInteger>(rhs).getLoc(), resultTy); case nonloc::ConcreteIntKind: { // Transform the integer into a location and compare. @@ -246,7 +308,7 @@ SVal SimpleSValuator::EvalBinOpNN(const GRState *state, llvm::APSInt i = cast<nonloc::ConcreteInt>(rhs).getValue(); i.setIsUnsigned(true); i.extOrTrunc(Ctx.getTypeSize(Ctx.VoidPtrTy)); - return EvalBinOpLL(op, lhsL, ValMgr.makeLoc(i), resultTy); + return EvalBinOpLL(state, op, lhsL, ValMgr.makeLoc(i), resultTy); } default: switch (op) { @@ -261,87 +323,136 @@ SVal SimpleSValuator::EvalBinOpNN(const GRState *state, } } case nonloc::SymExprValKind: { - // Logical not? - if (!(op == BinaryOperator::EQ && rhs.isZeroConstant())) + nonloc::SymExprVal *selhs = cast<nonloc::SymExprVal>(&lhs); + + // Only handle LHS of the form "$sym op constant", at least for now. + const SymIntExpr *symIntExpr = + dyn_cast<SymIntExpr>(selhs->getSymbolicExpression()); + + if (!symIntExpr) return UnknownVal(); - const SymExpr *symExpr = - cast<nonloc::SymExprVal>(lhs).getSymbolicExpression(); + // Is this a logical not? (!x is represented as x == 0.) + if (op == BinaryOperator::EQ && rhs.isZeroConstant()) { + // We know how to negate certain expressions. Simplify them here. - // Only handle ($sym op constant) for now. - if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(symExpr)) { BinaryOperator::Opcode opc = symIntExpr->getOpcode(); switch (opc) { - case BinaryOperator::LAnd: - case BinaryOperator::LOr: - assert(false && "Logical operators handled by branching logic."); - return UnknownVal(); - case BinaryOperator::Assign: - case BinaryOperator::MulAssign: - case BinaryOperator::DivAssign: - case BinaryOperator::RemAssign: - case BinaryOperator::AddAssign: - case BinaryOperator::SubAssign: - case BinaryOperator::ShlAssign: - case BinaryOperator::ShrAssign: - case BinaryOperator::AndAssign: - case BinaryOperator::XorAssign: - case BinaryOperator::OrAssign: - case BinaryOperator::Comma: - assert(false && "'=' and ',' operators handled by GRExprEngine."); - return UnknownVal(); - case BinaryOperator::PtrMemD: - case BinaryOperator::PtrMemI: - assert(false && "Pointer arithmetic not handled here."); - return UnknownVal(); - case BinaryOperator::Mul: - case BinaryOperator::Div: - case BinaryOperator::Rem: - case BinaryOperator::Add: - case BinaryOperator::Sub: - case BinaryOperator::Shl: - case BinaryOperator::Shr: - case BinaryOperator::And: - case BinaryOperator::Xor: - case BinaryOperator::Or: - // Not handled yet. - return UnknownVal(); - case BinaryOperator::LT: - case BinaryOperator::GT: - case BinaryOperator::LE: - case BinaryOperator::GE: - case BinaryOperator::EQ: - case BinaryOperator::NE: - opc = NegateComparison(opc); - assert(symIntExpr->getType(ValMgr.getContext()) == resultTy); - return ValMgr.makeNonLoc(symIntExpr->getLHS(), opc, - symIntExpr->getRHS(), resultTy); + default: + // We don't know how to negate this operation. + // Just handle it as if it were a normal comparison to 0. + break; + case BinaryOperator::LAnd: + case BinaryOperator::LOr: + assert(false && "Logical operators handled by branching logic."); + return UnknownVal(); + case BinaryOperator::Assign: + case BinaryOperator::MulAssign: + case BinaryOperator::DivAssign: + case BinaryOperator::RemAssign: + case BinaryOperator::AddAssign: + case BinaryOperator::SubAssign: + case BinaryOperator::ShlAssign: + case BinaryOperator::ShrAssign: + case BinaryOperator::AndAssign: + case BinaryOperator::XorAssign: + case BinaryOperator::OrAssign: + case BinaryOperator::Comma: + assert(false && "'=' and ',' operators handled by GRExprEngine."); + return UnknownVal(); + case BinaryOperator::PtrMemD: + case BinaryOperator::PtrMemI: + assert(false && "Pointer arithmetic not handled here."); + return UnknownVal(); + case BinaryOperator::LT: + case BinaryOperator::GT: + case BinaryOperator::LE: + case BinaryOperator::GE: + case BinaryOperator::EQ: + case BinaryOperator::NE: + // Negate the comparison and make a value. + opc = NegateComparison(opc); + assert(symIntExpr->getType(ValMgr.getContext()) == resultTy); + return ValMgr.makeNonLoc(symIntExpr->getLHS(), opc, + symIntExpr->getRHS(), resultTy); } } + + // For now, only handle expressions whose RHS is a constant. + const nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs); + if (!rhsInt) + return UnknownVal(); + + // If both the LHS and the current expression are additive, + // fold their constants. + if (BinaryOperator::isAdditiveOp(op)) { + BinaryOperator::Opcode lop = symIntExpr->getOpcode(); + if (BinaryOperator::isAdditiveOp(lop)) { + BasicValueFactory &BVF = ValMgr.getBasicValueFactory(); + + // resultTy may not be the best type to convert to, but it's + // probably the best choice in expressions with mixed type + // (such as x+1U+2LL). The rules for implicit conversions should + // choose a reasonable type to preserve the expression, and will + // at least match how the value is going to be used. + const llvm::APSInt &first = + BVF.Convert(resultTy, symIntExpr->getRHS()); + const llvm::APSInt &second = + BVF.Convert(resultTy, rhsInt->getValue()); + + const llvm::APSInt *newRHS; + if (lop == op) + newRHS = BVF.EvaluateAPSInt(BinaryOperator::Add, first, second); + else + newRHS = BVF.EvaluateAPSInt(BinaryOperator::Sub, first, second); + return MakeSymIntVal(symIntExpr->getLHS(), lop, *newRHS, resultTy); + } + } + + // Otherwise, make a SymExprVal out of the expression. + return MakeSymIntVal(symIntExpr, op, rhsInt->getValue(), resultTy); } case nonloc::ConcreteIntKind: { + const nonloc::ConcreteInt& lhsInt = cast<nonloc::ConcreteInt>(lhs); + if (isa<nonloc::ConcreteInt>(rhs)) { - const nonloc::ConcreteInt& lhsInt = cast<nonloc::ConcreteInt>(lhs); return lhsInt.evalBinOp(ValMgr, op, cast<nonloc::ConcreteInt>(rhs)); - } - else { + } else { + const llvm::APSInt& lhsValue = lhsInt.getValue(); + // Swap the left and right sides and flip the operator if doing so // allows us to better reason about the expression (this is a form // of expression canonicalization). + // While we're at it, catch some special cases for non-commutative ops. NonLoc tmp = rhs; rhs = lhs; lhs = tmp; switch (op) { - case BinaryOperator::LT: op = BinaryOperator::GT; continue; - case BinaryOperator::GT: op = BinaryOperator::LT; continue; - case BinaryOperator::LE: op = BinaryOperator::GE; continue; - case BinaryOperator::GE: op = BinaryOperator::LE; continue; + case BinaryOperator::LT: + case BinaryOperator::GT: + case BinaryOperator::LE: + case BinaryOperator::GE: + op = ReverseComparison(op); + continue; case BinaryOperator::EQ: case BinaryOperator::NE: case BinaryOperator::Add: case BinaryOperator::Mul: + case BinaryOperator::And: + case BinaryOperator::Xor: + case BinaryOperator::Or: continue; + case BinaryOperator::Shr: + if (lhsValue.isAllOnesValue() && lhsValue.isSigned()) + // At this point lhs and rhs have been swapped. + return rhs; + // FALL-THROUGH + case BinaryOperator::Shl: + if (lhsValue == 0) + // At this point lhs and rhs have been swapped. + return rhs; + return UnknownVal(); default: return UnknownVal(); } @@ -377,9 +488,9 @@ SVal SimpleSValuator::EvalBinOpNN(const GRState *state, } if (isa<nonloc::ConcreteInt>(rhs)) { - return ValMgr.makeNonLoc(slhs->getSymbol(), op, - cast<nonloc::ConcreteInt>(rhs).getValue(), - resultTy); + return MakeSymIntVal(slhs->getSymbol(), op, + cast<nonloc::ConcreteInt>(rhs).getValue(), + resultTy); } return UnknownVal(); @@ -388,21 +499,301 @@ SVal SimpleSValuator::EvalBinOpNN(const GRState *state, } } -SVal SimpleSValuator::EvalBinOpLL(BinaryOperator::Opcode op, Loc lhs, Loc rhs, +// FIXME: all this logic will change if/when we have MemRegion::getLocation(). +SVal SimpleSValuator::EvalBinOpLL(const GRState *state, + BinaryOperator::Opcode op, + Loc lhs, Loc rhs, QualType resultTy) { - switch (op) { + // Only comparisons and subtractions are valid operations on two pointers. + // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15]. + // However, if a pointer is casted to an integer, EvalBinOpNN may end up + // calling this function with another operation (PR7527). We don't attempt to + // model this for now, but it could be useful, particularly when the + // "location" is actually an integer value that's been passed through a void*. + if (!(BinaryOperator::isComparisonOp(op) || op == BinaryOperator::Sub)) + return UnknownVal(); + + // Special cases for when both sides are identical. + if (lhs == rhs) { + switch (op) { default: + assert(false && "Unimplemented operation for two identical values"); return UnknownVal(); + case BinaryOperator::Sub: + return ValMgr.makeZeroVal(resultTy); case BinaryOperator::EQ: + case BinaryOperator::LE: + case BinaryOperator::GE: + return ValMgr.makeTruthVal(true, resultTy); case BinaryOperator::NE: - return EvalEquality(ValMgr, lhs, rhs, op == BinaryOperator::EQ, resultTy); case BinaryOperator::LT: case BinaryOperator::GT: - // FIXME: Generalize. For now, just handle the trivial case where - // the two locations are identical. - if (lhs == rhs) + return ValMgr.makeTruthVal(false, resultTy); + } + } + + switch (lhs.getSubKind()) { + default: + assert(false && "Ordering not implemented for this Loc."); + return UnknownVal(); + + case loc::GotoLabelKind: + // The only thing we know about labels is that they're non-null. + if (rhs.isZeroConstant()) { + switch (op) { + default: + break; + case BinaryOperator::Sub: + return EvalCastL(lhs, resultTy); + case BinaryOperator::EQ: + case BinaryOperator::LE: + case BinaryOperator::LT: return ValMgr.makeTruthVal(false, resultTy); + case BinaryOperator::NE: + case BinaryOperator::GT: + case BinaryOperator::GE: + return ValMgr.makeTruthVal(true, resultTy); + } + } + // There may be two labels for the same location, and a function region may + // have the same address as a label at the start of the function (depending + // on the ABI). + // FIXME: we can probably do a comparison against other MemRegions, though. + // FIXME: is there a way to tell if two labels refer to the same location? + return UnknownVal(); + + case loc::ConcreteIntKind: { + // If one of the operands is a symbol and the other is a constant, + // build an expression for use by the constraint manager. + if (SymbolRef rSym = rhs.getAsLocSymbol()) { + // We can only build expressions with symbols on the left, + // so we need a reversible operator. + if (!BinaryOperator::isComparisonOp(op)) + return UnknownVal(); + + const llvm::APSInt &lVal = cast<loc::ConcreteInt>(lhs).getValue(); + return ValMgr.makeNonLoc(rSym, ReverseComparison(op), lVal, resultTy); + } + + // If both operands are constants, just perform the operation. + if (loc::ConcreteInt *rInt = dyn_cast<loc::ConcreteInt>(&rhs)) { + BasicValueFactory &BVF = ValMgr.getBasicValueFactory(); + SVal ResultVal = cast<loc::ConcreteInt>(lhs).EvalBinOp(BVF, op, *rInt); + if (Loc *Result = dyn_cast<Loc>(&ResultVal)) + return EvalCastL(*Result, resultTy); + else + return UnknownVal(); + } + + // Special case comparisons against NULL. + // This must come after the test if the RHS is a symbol, which is used to + // build constraints. The address of any non-symbolic region is guaranteed + // to be non-NULL, as is any label. + assert(isa<loc::MemRegionVal>(rhs) || isa<loc::GotoLabel>(rhs)); + if (lhs.isZeroConstant()) { + switch (op) { + default: + break; + case BinaryOperator::EQ: + case BinaryOperator::GT: + case BinaryOperator::GE: + return ValMgr.makeTruthVal(false, resultTy); + case BinaryOperator::NE: + case BinaryOperator::LT: + case BinaryOperator::LE: + return ValMgr.makeTruthVal(true, resultTy); + } + } + + // Comparing an arbitrary integer to a region or label address is + // completely unknowable. + return UnknownVal(); + } + case loc::MemRegionKind: { + if (loc::ConcreteInt *rInt = dyn_cast<loc::ConcreteInt>(&rhs)) { + // If one of the operands is a symbol and the other is a constant, + // build an expression for use by the constraint manager. + if (SymbolRef lSym = lhs.getAsLocSymbol()) + return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy); + + // Special case comparisons to NULL. + // This must come after the test if the LHS is a symbol, which is used to + // build constraints. The address of any non-symbolic region is guaranteed + // to be non-NULL. + if (rInt->isZeroConstant()) { + switch (op) { + default: + break; + case BinaryOperator::Sub: + return EvalCastL(lhs, resultTy); + case BinaryOperator::EQ: + case BinaryOperator::LT: + case BinaryOperator::LE: + return ValMgr.makeTruthVal(false, resultTy); + case BinaryOperator::NE: + case BinaryOperator::GT: + case BinaryOperator::GE: + return ValMgr.makeTruthVal(true, resultTy); + } + } + + // Comparing a region to an arbitrary integer is completely unknowable. + return UnknownVal(); + } + + // Get both values as regions, if possible. + const MemRegion *LeftMR = lhs.getAsRegion(); + assert(LeftMR && "MemRegionKind SVal doesn't have a region!"); + + const MemRegion *RightMR = rhs.getAsRegion(); + if (!RightMR) + // The RHS is probably a label, which in theory could address a region. + // FIXME: we can probably make a more useful statement about non-code + // regions, though. + return UnknownVal(); + + // If both values wrap regions, see if they're from different base regions. + const MemRegion *LeftBase = LeftMR->getBaseRegion(); + const MemRegion *RightBase = RightMR->getBaseRegion(); + if (LeftBase != RightBase && + !isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) { + switch (op) { + default: + return UnknownVal(); + case BinaryOperator::EQ: + return ValMgr.makeTruthVal(false, resultTy); + case BinaryOperator::NE: + return ValMgr.makeTruthVal(true, resultTy); + } + } + + // The two regions are from the same base region. See if they're both a + // type of region we know how to compare. + + // FIXME: If/when there is a getAsRawOffset() for FieldRegions, this + // ElementRegion path and the FieldRegion path below should be unified. + if (const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR)) { + // First see if the right region is also an ElementRegion. + const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR); + if (!RightER) + return UnknownVal(); + + // Next, see if the two ERs have the same super-region and matching types. + // FIXME: This should do something useful even if the types don't match, + // though if both indexes are constant the RegionRawOffset path will + // give the correct answer. + if (LeftER->getSuperRegion() == RightER->getSuperRegion() && + LeftER->getElementType() == RightER->getElementType()) { + // Get the left index and cast it to the correct type. + // If the index is unknown or undefined, bail out here. + SVal LeftIndexVal = LeftER->getIndex(); + NonLoc *LeftIndex = dyn_cast<NonLoc>(&LeftIndexVal); + if (!LeftIndex) + return UnknownVal(); + LeftIndexVal = EvalCastNL(*LeftIndex, resultTy); + LeftIndex = dyn_cast<NonLoc>(&LeftIndexVal); + if (!LeftIndex) + return UnknownVal(); + + // Do the same for the right index. + SVal RightIndexVal = RightER->getIndex(); + NonLoc *RightIndex = dyn_cast<NonLoc>(&RightIndexVal); + if (!RightIndex) + return UnknownVal(); + RightIndexVal = EvalCastNL(*RightIndex, resultTy); + RightIndex = dyn_cast<NonLoc>(&RightIndexVal); + if (!RightIndex) + return UnknownVal(); + + // Actually perform the operation. + // EvalBinOpNN expects the two indexes to already be the right type. + return EvalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy); + } + + // If the element indexes aren't comparable, see if the raw offsets are. + RegionRawOffset LeftOffset = LeftER->getAsRawOffset(); + RegionRawOffset RightOffset = RightER->getAsRawOffset(); + + if (LeftOffset.getRegion() != NULL && + LeftOffset.getRegion() == RightOffset.getRegion()) { + int64_t left = LeftOffset.getByteOffset(); + int64_t right = RightOffset.getByteOffset(); + + switch (op) { + default: + return UnknownVal(); + case BinaryOperator::LT: + return ValMgr.makeTruthVal(left < right, resultTy); + case BinaryOperator::GT: + return ValMgr.makeTruthVal(left > right, resultTy); + case BinaryOperator::LE: + return ValMgr.makeTruthVal(left <= right, resultTy); + case BinaryOperator::GE: + return ValMgr.makeTruthVal(left >= right, resultTy); + case BinaryOperator::EQ: + return ValMgr.makeTruthVal(left == right, resultTy); + case BinaryOperator::NE: + return ValMgr.makeTruthVal(left != right, resultTy); + } + } + + // If we get here, we have no way of comparing the ElementRegions. return UnknownVal(); + } + + // See if both regions are fields of the same structure. + // FIXME: This doesn't handle nesting, inheritance, or Objective-C ivars. + if (const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR)) { + // Only comparisons are meaningful here! + if (!BinaryOperator::isComparisonOp(op)) + return UnknownVal(); + + // First see if the right region is also a FieldRegion. + const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR); + if (!RightFR) + return UnknownVal(); + + // Next, see if the two FRs have the same super-region. + // FIXME: This doesn't handle casts yet, and simply stripping the casts + // doesn't help. + if (LeftFR->getSuperRegion() != RightFR->getSuperRegion()) + return UnknownVal(); + + const FieldDecl *LeftFD = LeftFR->getDecl(); + const FieldDecl *RightFD = RightFR->getDecl(); + const RecordDecl *RD = LeftFD->getParent(); + + // Make sure the two FRs are from the same kind of record. Just in case! + // FIXME: This is probably where inheritance would be a problem. + if (RD != RightFD->getParent()) + return UnknownVal(); + + // We know for sure that the two fields are not the same, since that + // would have given us the same SVal. + if (op == BinaryOperator::EQ) + return ValMgr.makeTruthVal(false, resultTy); + if (op == BinaryOperator::NE) + return ValMgr.makeTruthVal(true, resultTy); + + // Iterate through the fields and see which one comes first. + // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field + // members and the units in which bit-fields reside have addresses that + // increase in the order in which they are declared." + bool leftFirst = (op == BinaryOperator::LT || op == BinaryOperator::LE); + for (RecordDecl::field_iterator I = RD->field_begin(), + E = RD->field_end(); I!=E; ++I) { + if (*I == LeftFD) + return ValMgr.makeTruthVal(leftFirst, resultTy); + if (*I == RightFD) + return ValMgr.makeTruthVal(!leftFirst, resultTy); + } + + assert(false && "Fields not found in parent record's definition"); + } + + // If we get here, we have no way of comparing the regions. + return UnknownVal(); + } } } @@ -414,7 +805,7 @@ SVal SimpleSValuator::EvalBinOpLN(const GRState *state, // triggered, but transfer functions like those for OSCommpareAndSwapBarrier32 // can generate comparisons that trigger this code. // FIXME: Are all locations guaranteed to have pointer width? - if (BinaryOperator::isEqualityOp(op)) { + if (BinaryOperator::isComparisonOp(op)) { if (nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs)) { const llvm::APSInt *x = &rhsInt->getValue(); ASTContext &ctx = ValMgr.getContext(); @@ -423,7 +814,7 @@ SVal SimpleSValuator::EvalBinOpLN(const GRState *state, if (x->isSigned()) x = &ValMgr.getBasicValueFactory().getValue(*x, true); - return EvalBinOpLL(op, lhs, loc::ConcreteInt(*x), resultTy); + return EvalBinOpLL(state, op, lhs, loc::ConcreteInt(*x), resultTy); } } } @@ -432,3 +823,21 @@ SVal SimpleSValuator::EvalBinOpLN(const GRState *state, return state->getStateManager().getStoreManager().EvalBinOp(op, lhs, rhs, resultTy); } + +const llvm::APSInt *SimpleSValuator::getKnownValue(const GRState *state, + SVal V) { + if (V.isUnknownOrUndef()) + return NULL; + + if (loc::ConcreteInt* X = dyn_cast<loc::ConcreteInt>(&V)) + return &X->getValue(); + + if (nonloc::ConcreteInt* X = dyn_cast<nonloc::ConcreteInt>(&V)) + return &X->getValue(); + + if (SymbolRef Sym = V.getAsSymbol()) + return state->getSymVal(Sym); + + // FIXME: Add support for SymExprs. + return NULL; +} diff --git a/lib/Checker/StackAddrLeakChecker.cpp b/lib/Checker/StackAddrLeakChecker.cpp new file mode 100644 index 000000000000..f4a9db62df4b --- /dev/null +++ b/lib/Checker/StackAddrLeakChecker.cpp @@ -0,0 +1,204 @@ +//=== StackAddrLeakChecker.cpp ------------------------------------*- C++ -*--// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines stack address leak checker, which checks if an invalid +// stack address is stored into a global or heap location. See CERT DCL30-C. +// +//===----------------------------------------------------------------------===// + +#include "GRExprEngineInternalChecks.h" +#include "clang/Checker/BugReporter/BugType.h" +#include "clang/Checker/PathSensitive/CheckerVisitor.h" +#include "clang/Checker/PathSensitive/GRState.h" +#include "clang/Basic/SourceManager.h" +#include "llvm/ADT/SmallString.h" +using namespace clang; + +namespace { +class StackAddrLeakChecker : public CheckerVisitor<StackAddrLeakChecker> { + BuiltinBug *BT_stackleak; + BuiltinBug *BT_returnstack; + +public: + StackAddrLeakChecker() : BT_stackleak(0), BT_returnstack(0) {} + static void *getTag() { + static int x; + return &x; + } + void PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *RS); + void EvalEndPath(GREndPathNodeBuilder &B, void *tag, GRExprEngine &Eng); +private: + void EmitStackError(CheckerContext &C, const MemRegion *R, const Expr *RetE); + SourceRange GenName(llvm::raw_ostream &os, const MemRegion *R, + SourceManager &SM); +}; +} + +void clang::RegisterStackAddrLeakChecker(GRExprEngine &Eng) { + Eng.registerCheck(new StackAddrLeakChecker()); +} + +SourceRange StackAddrLeakChecker::GenName(llvm::raw_ostream &os, + const MemRegion *R, + SourceManager &SM) { + // Get the base region, stripping away fields and elements. + R = R->getBaseRegion(); + SourceRange range; + os << "Address of "; + + // Check if the region is a compound literal. + if (const CompoundLiteralRegion* CR = dyn_cast<CompoundLiteralRegion>(R)) { + const CompoundLiteralExpr* CL = CR->getLiteralExpr(); + os << "stack memory associated with a compound literal " + "declared on line " + << SM.getInstantiationLineNumber(CL->getLocStart()) + << " returned to caller"; + range = CL->getSourceRange(); + } + else if (const AllocaRegion* AR = dyn_cast<AllocaRegion>(R)) { + const Expr* ARE = AR->getExpr(); + SourceLocation L = ARE->getLocStart(); + range = ARE->getSourceRange(); + os << "stack memory allocated by call to alloca() on line " + << SM.getInstantiationLineNumber(L); + } + else if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { + const BlockDecl *BD = BR->getCodeRegion()->getDecl(); + SourceLocation L = BD->getLocStart(); + range = BD->getSourceRange(); + os << "stack-allocated block declared on line " + << SM.getInstantiationLineNumber(L); + } + else if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { + os << "stack memory associated with local variable '" + << VR->getString() << '\''; + range = VR->getDecl()->getSourceRange(); + } + else { + assert(false && "Invalid region in ReturnStackAddressChecker."); + } + + return range; +} + +void StackAddrLeakChecker::EmitStackError(CheckerContext &C, const MemRegion *R, + const Expr *RetE) { + ExplodedNode *N = C.GenerateSink(); + + if (!N) + return; + + if (!BT_returnstack) + BT_returnstack=new BuiltinBug("Return of address to stack-allocated memory"); + + // Generate a report for this bug. + llvm::SmallString<512> buf; + llvm::raw_svector_ostream os(buf); + SourceRange range = GenName(os, R, C.getSourceManager()); + os << " returned to caller"; + RangedBugReport *report = new RangedBugReport(*BT_returnstack, os.str(), N); + report->addRange(RetE->getSourceRange()); + if (range.isValid()) + report->addRange(range); + + C.EmitReport(report); +} + +void StackAddrLeakChecker::PreVisitReturnStmt(CheckerContext &C, + const ReturnStmt *RS) { + + const Expr *RetE = RS->getRetValue(); + if (!RetE) + return; + + SVal V = C.getState()->getSVal(RetE); + const MemRegion *R = V.getAsRegion(); + + if (!R || !R->hasStackStorage()) + return; + + if (R->hasStackStorage()) { + EmitStackError(C, R, RetE); + return; + } +} + +void StackAddrLeakChecker::EvalEndPath(GREndPathNodeBuilder &B, void *tag, + GRExprEngine &Eng) { + SaveAndRestore<bool> OldHasGen(B.HasGeneratedNode); + const GRState *state = B.getState(); + + // Iterate over all bindings to global variables and see if it contains + // a memory region in the stack space. + class CallBack : public StoreManager::BindingsHandler { + private: + const StackFrameContext *CurSFC; + public: + llvm::SmallVector<std::pair<const MemRegion*, const MemRegion*>, 10> V; + + CallBack(const LocationContext *LCtx) + : CurSFC(LCtx->getCurrentStackFrame()) {} + + bool HandleBinding(StoreManager &SMgr, Store store, + const MemRegion *region, SVal val) { + + if (!isa<GlobalsSpaceRegion>(region->getMemorySpace())) + return true; + + const MemRegion *vR = val.getAsRegion(); + if (!vR) + return true; + + if (const StackSpaceRegion *SSR = + dyn_cast<StackSpaceRegion>(vR->getMemorySpace())) { + // If the global variable holds a location in the current stack frame, + // record the binding to emit a warning. + if (SSR->getStackFrame() == CurSFC) + V.push_back(std::make_pair(region, vR)); + } + + return true; + } + }; + + CallBack cb(B.getPredecessor()->getLocationContext()); + state->getStateManager().getStoreManager().iterBindings(state->getStore(),cb); + + if (cb.V.empty()) + return; + + // Generate an error node. + ExplodedNode *N = B.generateNode(state, tag, B.getPredecessor()); + if (!N) + return; + + if (!BT_stackleak) + BT_stackleak = + new BuiltinBug("Stack address stored into global variable", + "Stack address was saved into a global variable. " + "This is dangerous because the address will become " + "invalid after returning from the function"); + + for (unsigned i = 0, e = cb.V.size(); i != e; ++i) { + // Generate a report for this bug. + llvm::SmallString<512> buf; + llvm::raw_svector_ostream os(buf); + SourceRange range = GenName(os, cb.V[i].second, + Eng.getContext().getSourceManager()); + os << " is still referred to by the global variable '"; + const VarRegion *VR = cast<VarRegion>(cb.V[i].first->getBaseRegion()); + os << VR->getDecl()->getNameAsString() + << "' upon returning to the caller. This will be a dangling reference"; + RangedBugReport *report = new RangedBugReport(*BT_stackleak, os.str(), N); + if (range.isValid()) + report->addRange(range); + + Eng.getBugReporter().EmitReport(report); + } +} diff --git a/lib/Checker/Store.cpp b/lib/Checker/Store.cpp index c12065b89a04..b12833170506 100644 --- a/lib/Checker/Store.cpp +++ b/lib/Checker/Store.cpp @@ -91,7 +91,8 @@ const MemRegion *StoreManager::CastRegion(const MemRegion *R, QualType CastToTy) case MemRegion::StackArgumentsSpaceRegionKind: case MemRegion::HeapSpaceRegionKind: case MemRegion::UnknownSpaceRegionKind: - case MemRegion::GlobalsSpaceRegionKind: { + case MemRegion::NonStaticGlobalSpaceRegionKind: + case MemRegion::StaticGlobalSpaceRegionKind: { assert(0 && "Invalid region cast"); break; } @@ -232,17 +233,6 @@ SVal StoreManager::CastRetrievedVal(SVal V, const TypedRegion *R, return V; } -Store StoreManager::InvalidateRegions(Store store, - const MemRegion * const *I, - const MemRegion * const *End, - const Expr *E, unsigned Count, - InvalidatedSymbols *IS) { - for ( ; I != End ; ++I) - store = InvalidateRegion(store, *I, E, Count, IS); - - return store; -} - SVal StoreManager::getLValueFieldOrIvar(const Decl* D, SVal Base) { if (Base.isUnknownOrUndef()) return Base; diff --git a/lib/Checker/StreamChecker.cpp b/lib/Checker/StreamChecker.cpp new file mode 100644 index 000000000000..c527ca24496f --- /dev/null +++ b/lib/Checker/StreamChecker.cpp @@ -0,0 +1,287 @@ +//===-- StreamChecker.cpp -----------------------------------------*- C++ -*--// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines checkers that model and check stream handling functions. +// +//===----------------------------------------------------------------------===// + +#include "GRExprEngineExperimentalChecks.h" +#include "clang/Checker/BugReporter/BugType.h" +#include "clang/Checker/PathSensitive/CheckerVisitor.h" +#include "clang/Checker/PathSensitive/GRState.h" +#include "clang/Checker/PathSensitive/GRStateTrait.h" +#include "clang/Checker/PathSensitive/SymbolManager.h" +#include "llvm/ADT/ImmutableMap.h" + +using namespace clang; + +namespace { + +class StreamChecker : public CheckerVisitor<StreamChecker> { + IdentifierInfo *II_fopen, *II_fread, *II_fwrite, + *II_fseek, *II_ftell, *II_rewind, *II_fgetpos, *II_fsetpos, + *II_clearerr, *II_feof, *II_ferror, *II_fileno; + BuiltinBug *BT_nullfp, *BT_illegalwhence; + +public: + StreamChecker() + : II_fopen(0), II_fread(0), II_fwrite(0), + II_fseek(0), II_ftell(0), II_rewind(0), II_fgetpos(0), II_fsetpos(0), + II_clearerr(0), II_feof(0), II_ferror(0), II_fileno(0), + BT_nullfp(0), BT_illegalwhence(0) {} + + static void *getTag() { + static int x; + return &x; + } + + virtual bool EvalCallExpr(CheckerContext &C, const CallExpr *CE); + +private: + void Fopen(CheckerContext &C, const CallExpr *CE); + void Fread(CheckerContext &C, const CallExpr *CE); + void Fwrite(CheckerContext &C, const CallExpr *CE); + void Fseek(CheckerContext &C, const CallExpr *CE); + void Ftell(CheckerContext &C, const CallExpr *CE); + void Rewind(CheckerContext &C, const CallExpr *CE); + void Fgetpos(CheckerContext &C, const CallExpr *CE); + void Fsetpos(CheckerContext &C, const CallExpr *CE); + void Clearerr(CheckerContext &C, const CallExpr *CE); + void Feof(CheckerContext &C, const CallExpr *CE); + void Ferror(CheckerContext &C, const CallExpr *CE); + void Fileno(CheckerContext &C, const CallExpr *CE); + + // Return true indicates the stream pointer is NULL. + const GRState *CheckNullStream(SVal SV, const GRState *state, + CheckerContext &C); +}; + +} // end anonymous namespace + +void clang::RegisterStreamChecker(GRExprEngine &Eng) { + Eng.registerCheck(new StreamChecker()); +} + +bool StreamChecker::EvalCallExpr(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + const Expr *Callee = CE->getCallee(); + SVal L = state->getSVal(Callee); + const FunctionDecl *FD = L.getAsFunctionDecl(); + if (!FD) + return false; + + ASTContext &Ctx = C.getASTContext(); + if (!II_fopen) + II_fopen = &Ctx.Idents.get("fopen"); + if (!II_fread) + II_fread = &Ctx.Idents.get("fread"); + if (!II_fwrite) + II_fwrite = &Ctx.Idents.get("fwrite"); + if (!II_fseek) + II_fseek = &Ctx.Idents.get("fseek"); + if (!II_ftell) + II_ftell = &Ctx.Idents.get("ftell"); + if (!II_rewind) + II_rewind = &Ctx.Idents.get("rewind"); + if (!II_fgetpos) + II_fgetpos = &Ctx.Idents.get("fgetpos"); + if (!II_fsetpos) + II_fsetpos = &Ctx.Idents.get("fsetpos"); + if (!II_clearerr) + II_clearerr = &Ctx.Idents.get("clearerr"); + if (!II_feof) + II_feof = &Ctx.Idents.get("feof"); + if (!II_ferror) + II_ferror = &Ctx.Idents.get("ferror"); + if (!II_fileno) + II_fileno = &Ctx.Idents.get("fileno"); + + if (FD->getIdentifier() == II_fopen) { + Fopen(C, CE); + return true; + } + if (FD->getIdentifier() == II_fread) { + Fread(C, CE); + return true; + } + if (FD->getIdentifier() == II_fwrite) { + Fwrite(C, CE); + return true; + } + if (FD->getIdentifier() == II_fseek) { + Fseek(C, CE); + return true; + } + if (FD->getIdentifier() == II_ftell) { + Ftell(C, CE); + return true; + } + if (FD->getIdentifier() == II_rewind) { + Rewind(C, CE); + return true; + } + if (FD->getIdentifier() == II_fgetpos) { + Fgetpos(C, CE); + return true; + } + if (FD->getIdentifier() == II_fsetpos) { + Fsetpos(C, CE); + return true; + } + if (FD->getIdentifier() == II_clearerr) { + Clearerr(C, CE); + return true; + } + if (FD->getIdentifier() == II_feof) { + Feof(C, CE); + return true; + } + if (FD->getIdentifier() == II_ferror) { + Ferror(C, CE); + return true; + } + if (FD->getIdentifier() == II_fileno) { + Fileno(C, CE); + return true; + } + + return false; +} + +void StreamChecker::Fopen(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + unsigned Count = C.getNodeBuilder().getCurrentBlockCount(); + ValueManager &ValMgr = C.getValueManager(); + DefinedSVal RetVal = cast<DefinedSVal>(ValMgr.getConjuredSymbolVal(0, CE, + Count)); + state = state->BindExpr(CE, RetVal); + + ConstraintManager &CM = C.getConstraintManager(); + // Bifurcate the state into two: one with a valid FILE* pointer, the other + // with a NULL. + const GRState *stateNotNull, *stateNull; + llvm::tie(stateNotNull, stateNull) = CM.AssumeDual(state, RetVal); + + C.addTransition(stateNotNull); + C.addTransition(stateNull); +} + +void StreamChecker::Fread(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + if (!CheckNullStream(state->getSVal(CE->getArg(3)), state, C)) + return; +} + +void StreamChecker::Fwrite(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + if (!CheckNullStream(state->getSVal(CE->getArg(3)), state, C)) + return; +} + +void StreamChecker::Fseek(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + if (!(state = CheckNullStream(state->getSVal(CE->getArg(0)), state, C))) + return; + // Check the legality of the 'whence' argument of 'fseek'. + SVal Whence = state->getSVal(CE->getArg(2)); + bool WhenceIsLegal = true; + const nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Whence); + if (!CI) + WhenceIsLegal = false; + + int64_t x = CI->getValue().getSExtValue(); + if (!(x == 0 || x == 1 || x == 2)) + WhenceIsLegal = false; + + if (!WhenceIsLegal) { + if (ExplodedNode *N = C.GenerateSink(state)) { + if (!BT_illegalwhence) + BT_illegalwhence = new BuiltinBug("Illegal whence argument", + "The whence argument to fseek() should be " + "SEEK_SET, SEEK_END, or SEEK_CUR."); + BugReport *R = new BugReport(*BT_illegalwhence, + BT_illegalwhence->getDescription(), N); + C.EmitReport(R); + } + return; + } + + C.addTransition(state); +} + +void StreamChecker::Ftell(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + if (!CheckNullStream(state->getSVal(CE->getArg(0)), state, C)) + return; +} + +void StreamChecker::Rewind(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + if (!CheckNullStream(state->getSVal(CE->getArg(0)), state, C)) + return; +} + +void StreamChecker::Fgetpos(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + if (!CheckNullStream(state->getSVal(CE->getArg(0)), state, C)) + return; +} + +void StreamChecker::Fsetpos(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + if (!CheckNullStream(state->getSVal(CE->getArg(0)), state, C)) + return; +} + +void StreamChecker::Clearerr(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + if (!CheckNullStream(state->getSVal(CE->getArg(0)), state, C)) + return; +} + +void StreamChecker::Feof(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + if (!CheckNullStream(state->getSVal(CE->getArg(0)), state, C)) + return; +} + +void StreamChecker::Ferror(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + if (!CheckNullStream(state->getSVal(CE->getArg(0)), state, C)) + return; +} + +void StreamChecker::Fileno(CheckerContext &C, const CallExpr *CE) { + const GRState *state = C.getState(); + if (!CheckNullStream(state->getSVal(CE->getArg(0)), state, C)) + return; +} + +const GRState *StreamChecker::CheckNullStream(SVal SV, const GRState *state, + CheckerContext &C) { + const DefinedSVal *DV = dyn_cast<DefinedSVal>(&SV); + if (!DV) + return 0; + + ConstraintManager &CM = C.getConstraintManager(); + const GRState *stateNotNull, *stateNull; + llvm::tie(stateNotNull, stateNull) = CM.AssumeDual(state, *DV); + + if (!stateNotNull && stateNull) { + if (ExplodedNode *N = C.GenerateSink(stateNull)) { + if (!BT_nullfp) + BT_nullfp = new BuiltinBug("NULL stream pointer", + "Stream pointer might be NULL."); + BugReport *R =new BugReport(*BT_nullfp, BT_nullfp->getDescription(), N); + C.EmitReport(R); + } + return 0; + } + return stateNotNull; +} diff --git a/lib/Checker/SymbolManager.cpp b/lib/Checker/SymbolManager.cpp index f3a803c57d32..c2b557ea57db 100644 --- a/lib/Checker/SymbolManager.cpp +++ b/lib/Checker/SymbolManager.cpp @@ -74,6 +74,10 @@ void SymbolDerived::dumpToStream(llvm::raw_ostream& os) const { << getParentSymbol() << ',' << getRegion() << '}'; } +void SymbolExtent::dumpToStream(llvm::raw_ostream& os) const { + os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; +} + void SymbolRegionValue::dumpToStream(llvm::raw_ostream& os) const { os << "reg_$" << getSymbolID() << "<" << R << ">"; } @@ -130,6 +134,22 @@ SymbolManager::getDerivedSymbol(SymbolRef parentSymbol, return cast<SymbolDerived>(SD); } +const SymbolExtent* +SymbolManager::getExtentSymbol(const SubRegion *R) { + llvm::FoldingSetNodeID profile; + SymbolExtent::Profile(profile, R); + void* InsertPos; + SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); + if (!SD) { + SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>(); + new (SD) SymbolExtent(SymbolCounter, R); + DataSet.InsertNode(SD, InsertPos); + ++SymbolCounter; + } + + return cast<SymbolExtent>(SD); +} + const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const llvm::APSInt& v, @@ -170,11 +190,14 @@ QualType SymbolConjured::getType(ASTContext&) const { return T; } - QualType SymbolDerived::getType(ASTContext& Ctx) const { return R->getValueType(Ctx); } +QualType SymbolExtent::getType(ASTContext& Ctx) const { + return Ctx.getSizeType(); +} + QualType SymbolRegionValue::getType(ASTContext& C) const { return R->getValueType(C); } @@ -210,16 +233,25 @@ bool SymbolReaper::isLive(SymbolRef sym) { return false; } + if (const SymbolExtent *extent = dyn_cast<SymbolExtent>(sym)) { + const MemRegion *Base = extent->getRegion()->getBaseRegion(); + if (const VarRegion *VR = dyn_cast<VarRegion>(Base)) + return isLive(VR); + if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Base)) + return isLive(SR->getSymbol()); + return false; + } + // Interogate the symbol. It may derive from an input value to // the analyzed function/method. return isa<SymbolRegionValue>(sym); } -bool SymbolReaper::isLive(const Stmt* Loc, const Stmt* ExprVal) const { +bool SymbolReaper::isLive(const Stmt* ExprVal) const { return LCtx->getLiveVariables()->isLive(Loc, ExprVal); } -bool SymbolReaper::isLive(const Stmt *Loc, const VarRegion *VR) const { +bool SymbolReaper::isLive(const VarRegion *VR) const { const StackFrameContext *SFC = VR->getStackFrame(); if (SFC == LCtx->getCurrentStackFrame()) diff --git a/lib/Checker/VLASizeChecker.cpp b/lib/Checker/VLASizeChecker.cpp index cea9d191aa77..936991d6133c 100644 --- a/lib/Checker/VLASizeChecker.cpp +++ b/lib/Checker/VLASizeChecker.cpp @@ -9,10 +9,13 @@ // // This defines VLASizeChecker, a builtin check in GRExprEngine that // performs checks for declaration of VLA of undefined or zero size. +// In addition, VLASizeChecker is responsible for defining the extent +// of the MemRegion that represents a VLA. // //===----------------------------------------------------------------------===// #include "GRExprEngineInternalChecks.h" +#include "clang/AST/CharUnits.h" #include "clang/Checker/BugReporter/BugType.h" #include "clang/Checker/PathSensitive/CheckerVisitor.h" #include "clang/Checker/PathSensitive/GRExprEngine.h" @@ -42,9 +45,9 @@ void VLASizeChecker::PreVisitDeclStmt(CheckerContext &C, const DeclStmt *DS) { const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); if (!VD) return; - - const VariableArrayType *VLA - = C.getASTContext().getAsVariableArrayType(VD->getType()); + + ASTContext &Ctx = C.getASTContext(); + const VariableArrayType *VLA = Ctx.getAsVariableArrayType(VD->getType()); if (!VLA) return; @@ -70,9 +73,14 @@ void VLASizeChecker::PreVisitDeclStmt(CheckerContext &C, const DeclStmt *DS) { C.EmitReport(report); return; } + + // See if the size value is known. It can't be undefined because we would have + // warned about that already. + if (sizeV.isUnknown()) + return; // Check if the size is zero. - DefinedOrUnknownSVal sizeD = cast<DefinedOrUnknownSVal>(sizeV); + DefinedSVal sizeD = cast<DefinedSVal>(sizeV); const GRState *stateNotZero, *stateZero; llvm::tie(stateNotZero, stateZero) = state->Assume(sizeD); @@ -92,5 +100,36 @@ void VLASizeChecker::PreVisitDeclStmt(CheckerContext &C, const DeclStmt *DS) { } // From this point on, assume that the size is not zero. - C.addTransition(stateNotZero); + state = stateNotZero; + + // VLASizeChecker is responsible for defining the extent of the array being + // declared. We do this by multiplying the array length by the element size, + // then matching that with the array region's extent symbol. + + // Convert the array length to size_t. + ValueManager &ValMgr = C.getValueManager(); + SValuator &SV = ValMgr.getSValuator(); + QualType SizeTy = Ctx.getSizeType(); + NonLoc ArrayLength = cast<NonLoc>(SV.EvalCast(sizeD, SizeTy, SE->getType())); + + // Get the element size. + CharUnits EleSize = Ctx.getTypeSizeInChars(VLA->getElementType()); + SVal EleSizeVal = ValMgr.makeIntVal(EleSize.getQuantity(), SizeTy); + + // Multiply the array length by the element size. + SVal ArraySizeVal = SV.EvalBinOpNN(state, BinaryOperator::Mul, ArrayLength, + cast<NonLoc>(EleSizeVal), SizeTy); + + // Finally, Assume that the array's extent matches the given size. + const LocationContext *LC = C.getPredecessor()->getLocationContext(); + DefinedOrUnknownSVal Extent = state->getRegion(VD, LC)->getExtent(ValMgr); + DefinedOrUnknownSVal ArraySize = cast<DefinedOrUnknownSVal>(ArraySizeVal); + DefinedOrUnknownSVal SizeIsKnown = SV.EvalEQ(state, Extent, ArraySize); + state = state->Assume(SizeIsKnown, true); + + // Assume should not fail at this point. + assert(state); + + // Remember our assumptions! + C.addTransition(state); } |