[cfe-dev] Check virtual calls in ctor or dtor
Ted Kremenek
kremenek at apple.com
Tue Nov 22 22:11:40 PST 2011
On Nov 11, 2011, at 12:56 AM, 章磊 wrote:
> Hi Ted,
>
> I re-implement this checker again.
>
> This time i introduce several data structure to do DP and the bugreport.
> I modified the worklist a bit, now its unit is a <FunctionDecl *, CallExpr *> pair from the caller's function decl to the call expr.
> RuntimeStack(vector of CallExpr) to simulate the call graph dynamiclly. This is for report the entire chain of the call path.
> A DenseMap from a FunctionDecl to all call paths in its body.
> A SmallPtrSet to Record which functions have be fully handled. A function fully handled means that all function bodies it called have been handled.
Hi Lei,
Thanks for continuing to refine the checker. I'll make specific comments inline on the patch below.
> I could not find a right way for this kind of bug report, it's not path diagnostic and we need to annotate the call expr in the call path. So i simply output the name with " <-- " to show the call-called relationship.
Ironically, the kind of report you are looking for is something that Clang's primary diagnostic system handles well, but the static analyzer's diagnostics does not. Since this is not a path-sensitive analysis, what essentially you want is a call-tree, represented with a single diagnostic and a collection of "notes". This is how diagnostics are done in Clang's warnings, but we don't have support for notes in the analyzer diagnostics.
For now, I think constructing a painfully long diagnostic is acceptable, but the long term solution is to enhance analyzer diagnostics to support notes as well.
> It will crash on some code because "Name is not a simple identifier"? But if we use the SourceRange, there would not be any crash like this, right?
No, unfortunately, this isn't acceptable, and using a SourceRange doesn't change the situation. There are plenty of times where the name of a method won't be a simple identifier, especially in C++. Fortunately, you can just use 'getNameAsString()' instead, and it won't crash.
>
> And i left several things unconsidered.
> The memory consume and reclaim.
The checker cannot leak memory, so we need to address this (if necessary). It looks to me like there aren't any issues, however. Nothing looks dynamically allocated using the 'new' operator, and the WalkAST object has finite lifetime, so I think everything will get automatically memory managed.
> The readabiliy of the code. It's a little hard to read now.
The code can definitely benefit from a bit more refactoring. For example, error reporting is duplicating in multiple places.
What I'd also like to see is some comments in the 'Execute' method that actually describes the algorithm. I think that's the main missing piece.
> Do you have any advices on these?
>
More comments inline in the patch:
> --- lib/StaticAnalyzer/Checkers/VirtualCallChecker.cpp (revision 0)
> +++ lib/StaticAnalyzer/Checkers/VirtualCallChecker.cpp (revision 0)
> @@ -0,0 +1,334 @@
> +//=======- VirtualCallChecker.cpp - Basic security checks --------*- 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 checker that checks virtual function calls during
> +// construction or destruction.
> +//
> +//===----------------------------------------------------------------------===//
> +
> +#include "ClangSACheckers.h"
> +#include "clang/StaticAnalyzer/Core/Checker.h"
> +#include "clang/AST/DeclCXX.h"
> +#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
> +#include "clang/AST/StmtVisitor.h"
> +#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
> +
> +using namespace clang;
> +using namespace ento;
> +
> +namespace {
> +
> +class WalkAST : public StmtVisitor<WalkAST> {
> + BugReporter &BR;
> + AnalysisDeclContext *AC;
> +
> + // WorkList using stack.
> + typedef std::pair<const FunctionDecl *, const CallExpr *> TyWorkListUnit;
> + SmallVector<TyWorkListUnit, 20> Stack;
I typically prefer 'WorkListUnitTy' as opposed to 'TyWorkListUnit'. Similarly, I expected the Stack type to also be typedef'ed, e.g.:
typedef SmallVector<WorkListUnitTy, 20> WorkListTy;
WorkListTy WorkList;
OR
typedef std::pair<const FunctionDecl *, const CallExpr *> WorkListUnit;
typedef SmallVector<WorkListUnit, 20> WorkList;
WorkList WList;
This keeps the type names cleaner and the name of the worklist object succinct.
> +
> + // Runtime Stack to record call path.
> + SmallVector<const CallExpr *, 20> RuntimeStack;
Also, consider using a typedef, which ties in with my next comment. For example:
typedef SmallVector<const CallExpr *, 20> CallChain;
typedef SmallVectorImpl<const CallExpr *> CallChainImpl;
CallChain RuntimeStack;
> +
> + // DenseMap from FunctionDecl* to all call paths in its body.
> + llvm::DenseMap<const FunctionDecl *,
> + SmallVector<SmallVector<const CallExpr *,20>,
> + 20> > VirtualCallsMap;
This is going to result with unnecessary malloc traffic, as any time the DenseMap gets resized all of the SmallVectors will get copied and destroyed. Instead, try:
typedef llvm::DenseMap<const FunctionDecl *, CallChainImpl *> CallsMap;
CallsMap VirtualCallsMap;
This will require dynamically allocating CallChain objects, which will need to be manually destroyed, but this will be way more efficient.
> +
> + // Current working FunctionDecl.
> + const FunctionDecl *Current;
Why is this state even needed?
> +
> + // Record which functions have be fully handled. A function fully handled
> + // means that all function bodies it called have been handled.
> + llvm::SmallPtrSet<const FunctionDecl *, 256> CheckedFunctions;
> +
'256' isn't really "small" anymore. Not sure if this is an actual performance issue, but I'd use a DenseSet instead. Try:
llvm::DenseSet<const FunctionDecl *> CheckedFunctions;
> +public:
> + WalkAST(BugReporter &br, AnalysisDeclContext *ac) : BR(br), AC(ac) {
> + Current = NULL;
> + }
'Current' can be initialized to NULL in the initializer list as well.
> +
> + bool hasWork() const {
> + return !Stack.empty();
> + }
Looks fine.
> +
> + void push(TyWorkListUnit WLUnit) {
> + Stack.push_back(WLUnit);
> + }
void push(WorkListUnit WLUnit)
is much cleaner.
> +
> + TyWorkListUnit pop() {
> + assert (!Stack.empty());
> + TyWorkListUnit WLUnit = Stack.back();
> + Stack.pop_back();
> +
> + return WLUnit;
> + }
I'd rename this to 'pop_back()'. 'pop()' in most data structures just pops the element without actually returning it.
> +
> + void Execute() {
Please add a big comment here, explaining what this method does.
> + while (hasWork()) {
> + TyWorkListUnit WLUnit = pop();
> + const FunctionDecl *FD = WLUnit.second->getDirectCallee();
> + assert(FD && FD->getBody());
> +
> + // Pop the RuntimeStack top, until the top is caller of current WLUnit.
> + while (!RuntimeStack.empty()) {
> + // get the top of runtime stack
Minor: please keep the comment style consistent. Start with a capital letter, and end with a '.'
> + const CallExpr *Top = RuntimeStack.back();
> + if (WLUnit.first == Top->getDirectCallee())
> + break;
> +
> + // When we pop_back a CallExpr from the RuntimeStack, its body has been
> + // fully checked.
> + CheckedFunctions.insert(Top->getDirectCallee());
> +
> + RuntimeStack.pop_back();
> + }
> + // After we find where is the top of the RuntimeStack, push the CallExpr
> + // into RuntimeStack.
> + RuntimeStack.push_back(WLUnit.second);
> +
> + // set Current to FD.
Minor: please keep the comment style consistent. Start with a capital letter, and end with a '.'
> + Current = FD;
> +
> + // Visit the body.
> + Visit(FD->getBody());
> + }
> +
> + // TODO: cleanup the RuntimeStack.
> + RuntimeStack.clear();
I don't know what this TODO implies. Can you clarify? I think if the worklist empties out, and as long as RuntimeStack doesn't contain anything that its destructor can't automatically cleanup, there is nothing to worry about.
> + }
> +
> + // Stmt visitor methods.
> + void VisitCallExpr(CallExpr *CE);
> + void VisitCXXMemberCallExpr(CallExpr *CE);
> + void VisitStmt(Stmt *S) { VisitChildren(S); }
> + void VisitChildren(Stmt *S);
> +
> + void VisitCXXConstructorDecl(CXXConstructorDecl *Ctor) {
> + if (Ctor && Ctor->getBody()) {
> + Current = Ctor;
> + Visit(Ctor->getBody());
> + }
> +
> + // After visit the body of the CXXConstructorDecl, execute the worklist.
> + Execute();
Why do we need to recursively call 'Execute'? Won't we already be processing the worklist?
> + }
> +
> + void VisitCXXDestructorDecl(CXXDestructorDecl *Dtor) {
> + if (Dtor && Dtor->getBody()){
> + Current = Dtor;
> + Visit(Dtor->getBody());
> + }
> +
> + // After visit the body of the CXXDestructorDecl, execute the worklist.
> + Execute();
Why do we need to recursively call 'Execute'? Won't we already be processing the worklist?
> + }
> +
> + void ReportVirtualCall(const CallExpr *CE, llvm::raw_svector_ostream &os);
> +
> +};
> +} // end anonymous namespace
> +
> +//===----------------------------------------------------------------------===//
> +// AST walking.
> +//===----------------------------------------------------------------------===//
> +
> +void WalkAST::VisitChildren(Stmt *S) {
> + for (Stmt::child_iterator I = S->child_begin(), E = S->child_end(); I!=E; ++I)
> + if (Stmt *child = *I)
> + Visit(child);
> +}
> +
> +void WalkAST::VisitCallExpr(CallExpr *CE) {
> + VisitChildren(CE);
> +
> + // Get the callee.
> + const FunctionDecl *FD = CE->getDirectCallee();
> + if (!FD)
> + return;
> +
> + // If FD is already fully checked, no need to push the body into worklist
> + // again.
> + if (CheckedFunctions.count(FD)) {
> +
> + // get the runtime stack depth.
Minor: please keep the comment style consistent. Start with a capital letter, and end with a '.'
> + unsigned StackDepth = RuntimeStack.size();
> +
> + // If there are virtual calls in the body of FD, we need to generate new
> + // bug reports. Otherwise we will do nothing.
> + if (VirtualCallsMap.count(FD)) {
> + for (unsigned i = 0; i < VirtualCallsMap[FD].size(); i++) {
> +
> + // Update virtual call paths of current function.
> + VirtualCallsMap[Current].push_back(VirtualCallsMap[FD][i]);
> + VirtualCallsMap[Current][VirtualCallsMap[Current].size()-1].
> + push_back(CE);
This is a bit gross and really inefficient. Please hoist the VirtualCallsMap[FD].size() out of the loop, or better yet, do a find for the entry so you don't lazily create entries that don't need to exist (you avoid this with the call to 'count', but this double lookup is a bit wasteful). This is a bunch of hashtable lookups to the same entry, when is really inefficient. Consider:
// If there are virtual calls in the body of FD, we need to generate new
// bug reports. Otherwise we will do nothing.
CallsMap::iterator I = VirtualCallsMap.find(FD);
if (I == VirtualCallsMap.end())
return;
assert(I->second);
CallChainImpl &Chain = *I->second;
for (Chain::iterator it = Chain.begin(), et = Chain.end(); it != et; ++it) {
// Update virtual call paths of current function.
CallChainImpl *&CurrentChain = VirtualCallsMap[Current];
if (!CurrentChain)
CurrentChain = new CallChain();
CurrentChain->push_back(*it);
CurrentChain->back().push_back(CE);
This is much more efficient.
> +
> + // Generate the call path string for bug report.
> + llvm::SmallString<100> buf;
> + llvm::raw_svector_ostream os(buf);
> +
> + os << "\n" << VirtualCallsMap[FD][i][0]->getDirectCallee()->getName();
> + for (unsigned j = 1; j < VirtualCallsMap[FD][i].size(); i++)
> + os << " <-- "
> + << VirtualCallsMap[FD][i][j]->getDirectCallee()->getName();
> +
> + os << " <-- " << CE->getDirectCallee()->getName();
> + for (unsigned k = 1; k <= StackDepth; k++)
> + // R[i] = RuntimeStack[StackDepth-i]->getCallee()->getSourceRange();
> + os << " <-- "
> + << RuntimeStack[StackDepth-k]->getDirectCallee()->getName();
> +
> + os << "\n" ;
This string generation logic looks identical to the logic in VisitCXXMemberCallExpr. Why can't this just be refactored into ReportVirtualCall, or into a separate method which generates the string in the SmallString which we then just pass to ReportVirtualCall as a StringRef? We shouldn't be copy-pasting string generation logic, as it means if we change it we need to change it in multiple places.
There is also a ton of redundant lookups to VirtualCallsMap. Those aren't free. While strictly speaking not a performance issue here (since it occurs when generating a bug report), we generally like to enforce the same kind of good performance conventions everywhere in the codebase to encourage best practice. Please clean it up using the same kind of tricks I used just above.
> +
> + ReportVirtualCall(VirtualCallsMap[FD][i][0], os);
No need to do yet another lookup to VirtualCallsMap[FD]. We already have the CurrentChain object.
> + }
> + }
> +
> + return;
> + }
> +
> + if (FD->getBody())
> + push(std::make_pair(Current, CE));
Looks good.
> +}
> +
> +void WalkAST::VisitCXXMemberCallExpr(CallExpr *CE) {
> + VisitChildren(CE);
> +
> + // If there is a qualifier to this CallExpr, return.
> + if (MemberExpr *CME = dyn_cast<MemberExpr>(CE->getCallee())) {
> + if (CME->getQualifier())
> + return;
> + }
> +
> + // Get the callee.
> + const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(CE->getDirectCallee());
> + if (!MD)
> + return;
> +
> + // get the runtime stack depth.
> + unsigned StackDepth = RuntimeStack.size();
> +
> + if (MD->isVirtual()) {
> +
> + VirtualCallsMap[Current].
> + push_back(llvm::SmallVector<const CallExpr *, 20>(1, CE));
Do not create container objects in this way. This implicitly results in a temporary object getting created, and then copied. Instead:
CallChainImpl *Chain = new CallChain()l
Chain->push_back(CE);
VirtualCallsMap[Current] = Chain;
> +
> + llvm::SmallString<100> buf;
> + llvm::raw_svector_ostream os(buf);
> +
> + os << "\n" << CE->getDirectCallee()->getName();
> + for (unsigned i = 1; i <= StackDepth; i++)
> + // R[i] = RuntimeStack[StackDepth-i]->getCallee()->getSourceRange();
> + os << " <-- " << RuntimeStack[StackDepth-i]->getDirectCallee()->getName();
> +
> + os << "\n" ;
> +
> + ReportVirtualCall(CE, os);
> +
> + // Do not check the body.
> + return;
> + }
> +
> + // If the MethodDecl is already fully checked, no need to push the body into
> + // worklist again.
> + if (CheckedFunctions.count(MD)) {
> + // If there are virtual calls in the body of the MethodDecl, we need to
> + // generate new bug reports. Otherwise we should do nothing.
> + if (VirtualCallsMap.count(MD)) {
> + for (unsigned i = 0; i < VirtualCallsMap[MD].size(); i++) {
> +
> + VirtualCallsMap[Current].push_back(VirtualCallsMap[MD][i]);
> + VirtualCallsMap[Current][VirtualCallsMap[Current].size()-1].
> + push_back(CE);
> +
> + llvm::SmallString<100> buf;
> + llvm::raw_svector_ostream os(buf);
> +
> + os << "\n" << VirtualCallsMap[MD][i][0]->getDirectCallee()->getName();
> + for (unsigned j = 1; j < VirtualCallsMap[MD][i].size(); i++)
> + os << " <-- "
> + << VirtualCallsMap[MD][i][j]->getDirectCallee()->getName();
> +
> + os << " <-- " << CE->getDirectCallee()->getName();
> + for (unsigned k = 1; k <= StackDepth; k++)
> + // R[i] = RuntimeStack[StackDepth-i]->getCallee()->getSourceRange();
> + os << " <-- "
> + << RuntimeStack[StackDepth-k]->getDirectCallee()->getName();
> +
> + os << "\n" ;
> +
> + ReportVirtualCall(VirtualCallsMap[MD][i][0], os);
This logic is practically identical to the logic in VisitCallExpr(). This can be completely refactored to much simpler and avoid the duplication.
> + }
> + }
> +
> + return;
> + }
> +
> + // Push the body into the worklist.
> + if (MD->getBody())
> + push(std::make_pair(Current, CE));
> +}
> +
> +void WalkAST::ReportVirtualCall(const CallExpr *CE,
> + llvm::raw_svector_ostream &os) {
> + PathDiagnosticLocation CELoc =
> + PathDiagnosticLocation::createBegin(CE, BR.getSourceManager(), AC);
> + SourceRange R = CE->getCallee()->getSourceRange();
> +
> + // Get the callee.
> + const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(CE->getDirectCallee());
> +
> + if (MD->isPure()) {
> + os << "Call pure virtual functions during construction or "
> + << "destruction may leads undefined behaviour";
> + BR.EmitBasicReport("Call pure virtual function during construction or "
> + "Destruction",
> + "Cplusplus",
> + os.str(), CELoc, &R, 1);
> + return;
> + }
> + else {
> + os << "\n" << "Call virtual functions during construction or "
> + << "destruction will never go to a more derived class";
> + BR.EmitBasicReport("Call virtual function during construction or "
> + "Destruction",
> + "Cplusplus",
> + os.str(), CELoc, &R, 1);
> + return;
> + }
> +}
> +
> +//===----------------------------------------------------------------------===//
> +// VirtualCallChecker
> +//===----------------------------------------------------------------------===//
> +
> +namespace {
> +class VirtualCallChecker : public Checker<check::ASTDecl<CXXRecordDecl> > {
> +public:
> + void checkASTDecl(const CXXRecordDecl *RD, AnalysisManager& mgr,
> + BugReporter &BR) const {
> + WalkAST walker(BR, mgr.getAnalysisDeclContext(RD));
> +
> + // Check the constructors.
> + for (CXXRecordDecl::ctor_iterator I = RD->ctor_begin(), E = RD->ctor_end();
> + I != E; ++I) {
> + if (I->isCopyOrMoveConstructor())
> + continue;
> + walker.VisitCXXConstructorDecl(*I);
> + }
> +
> + // Check the destructor.
> + CXXDestructorDecl *DD = RD->getDestructor();
> + walker.VisitCXXDestructorDecl(DD);
> + }
> +};
> +}
> +
> +void ento::registerVirtualCallChecker(CheckerManager &mgr) {
> + mgr.registerChecker<VirtualCallChecker>();
> +}
I think my main high level concern, beyond the code duplication, is that the algorithm seems a bit hard to follow. For example, I see two code paths in VisitCallExpr(), one for the case where the body of the callee has been analyzed before, and another one where it has not. Error reporting seems duplicated in a bunch of places, which is likely because the logic isn't quite factored the way it should be.
Stepping back, I think it's worth re-evaluating the overall algorithm. Here's an abstraction that I think will help.
Essentially we are building a virtual function callgraph. Once we have the callgraph, we can determine if any of the constructors/destructors can call a virtual function. Here's a simple decoupling of the algorithm:
(1) Do a DFS worklist algorithm to build the callgraph. This is basically the walk you are doing now, but you don't have to do any error reporting. You also don't need to keep track of the current call stack; all you care about is the current function you are analyzing, and the functions it calls. The worklist just consists of enqueueing FunctionDecls, dequeing them and walking their bodies looking for calls. When you see a call, you add the called function to the set of functions called by that function. Of course we only want to restrict ourselves to calls on the 'this' object.
(2) Once you have the (sparse) callgraph, you can iterate over all the constructors and destructors (you can cache a list of them on the side while doing step 1). For each one, do a BFS over the callgraph, looking for virtual functions. The BFS can be done as a worklist. The advantage of using a BFS is you just report the shortest call chain from the constructor/destructor to the virtual function. For each constructor/destructor, only report calling a specific virtual function once.
(2a) As a refinement to (2), you can cache when certain functions *never* call a virtual function, thus pruning the search. This is an optional step to improve performance.
(2b) Error reporting comes down to just reporting a path through the callgraph. Thus error reporting just becomes centralized in one place. No code duplication.
The nice thing about this approach is you get a really nice separation of concerns. You decouple to problem of finding the call graph (which conceptually could be extended to incorporate path-sensitive information, etc.) from the process of finding a bug (a path through the callgraph from constructor to virtual function). You also decouple the string generation from the logic of finding bugs.
I hope my comments are not discouraging. I think you are on the right track. I think taking a step back and looking at how the algorithm could be restructured would be really beneficial to cleaning up the code and also potentially making the checker more powerful in the long run. I also think you should pay a bit more attention to the accesses to containers. While doing redundant hash table lookups on a error reporting case is not so bad, having redundant lookups in the fast path of the checker really adds unnecessary sluggishness to your code.
I hope this helps.
Cheers,
Ted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111122/5a3dd13b/attachment.html>
More information about the cfe-dev
mailing list