mate1214 created this revision.
mate1214 added reviewers: NoQ, george.karpenkov, dcoughlin.
Herald added subscribers: cfe-commits, Szelethus, mikhail.ramalho, a.sidorin,
szepet, mgorny.
Add StackSizeChecker to StaticAnalyzer
This checker can be used to warn about potential stack overflows
or be used to estimate the size of used stack space.
Both a clang static analyzer and a clang-tidy version exist.
The clang-tidy version references the StackUsageMeasuringVisitor
class included in this commit so it can only come after this.
Both versions work by examining function bodies via the AST,
the static analyzer version can follow and summarize the space
used by call chains, while the calng-tidy version can analyze
function bodies faster, one by one.
This version emits warnings if the estimated stack size surpasses
the StackUsageLimit parameter, which is measured in bytes and
defaults to 100000. Setting it to some small value can be used
to turn the checker into a statistical tool since the calculated
values are included in the warning messages.
The calculations used for the size estimations do not take into
account potential compile-time optimizations and contain some
minor simplifications. Only the information stored in the AST
is used and variable lifetime rules are respected. The
calculations in a particular function body are carried out by the
StackUsageMeasuringVisitor class, which gives a composite result
about a piece of the AST containing the maximal estimated space,
the space that remain in use after the execution of those lines
and flags about encountered variable length arrays or special
nodes that satisfy a given predicate (e.g.: templates).
The current version takes no special actions upon encountering
variable length arrays, the tidy version has a simple extra logic
for them. The tests are divided between the two versions, the
static analyzer ones are about the ability to calculate the size
of a complete call stack and the clang-tidy ones focus on
particular statements and expression types, this is referenced
in one of the comments of the test files for those who want
to use the test cases to understand the checker a little bit more.
The code favors readability and maintainability over performance
in some places.
Repository:
rC Clang
https://reviews.llvm.org/D52390
Files:
include/clang/StaticAnalyzer/Checkers/Checkers.td
include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h
lib/StaticAnalyzer/Checkers/CMakeLists.txt
lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp
lib/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.cpp
test/Analysis/stack-size-callchain.cpp
test/Analysis/stack-size.cpp
Index: test/Analysis/stack-size.cpp
===================================================================
--- /dev/null
+++ test/Analysis/stack-size.cpp
@@ -0,0 +1,59 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.core.StackSize -analyzer-config alpha.core.StackSize:StackUsageLimit=1 -std=c++11 -triple x86_64-unknown-linux-gnu -verify %s
+
+// In this test an integer is 4 bytes, a bool is 1 byte.
+// The analysis uses the same method of calculation as the misc-stack-size
+// checker in clang-tidy.
+// (see clang-tools-extra/test/clang-tidy/misc-stack-size.cpp for examples)
+
+// If a call happens in a function body, the stack space used by the function
+// will be registered as the space used up until that point. Each time the
+// execution of a function body is completely finished, the maximal amount
+// of space used is estimated and checked against the limit.
+
+// This function gets called multiple times. The space used is varying each time.
+int f(int X) { return X; } // expected-warning {{Estimated stack usage is 8 bytes}}
+ // expected-warning@-1 {{Estimated stack usage is 12 bytes}}
+
+// This function illustrates the partial summation ability.
+// Before each call, the stack usage at that point is registered,
+// so it can be added to the statistics of the called function.
+void linear() {
+ int X = 1;
+ f(X); // expected-warning {{Estimated stack usage is 4 bytes}}
+ int Y = 2;
+ f(Y); // expected-warning {{Estimated stack usage is 8 bytes}}
+} // expected-warning {{Estimated stack usage is 20 bytes}}
+
+// This function shows the ability of this checker to calculate with recursion
+// far as the analyzer follows it.
+void recursion(int N) {
+ int X;
+
+ if (N <= 0)
+ return; // expected-warning {{Estimated stack usage is 44 bytes}}
+
+ recursion(N - 1); // expected-warning {{Estimated stack usage is 8 bytes}}
+ // expected-warning@-1 {{Estimated stack usage is 16 bytes}}
+ // expected-warning@-2 {{Estimated stack usage is 24 bytes}}
+ // expected-warning@-3 {{Estimated stack usage is 20 bytes}}
+ // expected-warning@-4 {{Estimated stack usage is 28 bytes}}
+ // expected-warning@-5 {{Estimated stack usage is 36 bytes}}
+}
+
+// This is only included so recursion is called by the analyzer.
+void call_recursion() {
+ recursion(3);
+} // expected-warning {{Estimated stack usage is 8 bytes}}
+
+void simple_branching() {
+ int A = 1;
+ if (A < 2) {
+ f(A); // expected-warning {{Estimated stack usage is 4 bytes}}
+ } else {
+ //This branch is not executed so we do not get warnings here.
+ f(2 * A);
+ }
+ // We do get the maximal usage calculated with the never executed branch
+ // included.
+} // expected-warning {{Estimated stack usage is 20 bytes}}
+
Index: test/Analysis/stack-size-callchain.cpp
===================================================================
--- /dev/null
+++ test/Analysis/stack-size-callchain.cpp
@@ -0,0 +1,22 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.core.StackSize -analyzer-config alpha.core.StackSize:StackUsageLimit=200 -std=c++11 -triple x86_64-unknown-linux-gnu -verify %s
+
+// The checker accumulates variables from each level of the call chain.
+// In this case from function 'c' to 'a' each body has 10 long integers
+// on the stack, which accumulates to 30 * 8 = 240 bytes.
+
+void function_a() {
+ long A[10]; // expected-warning {{Estimated stack usage is 240 bytes}}
+}
+
+void function_b() {
+ long B1[10];
+ function_a();
+ long B2[5];
+}
+
+void function_c() {
+ long C1[10];
+ function_b();
+ long C2[5];
+}
+
Index: lib/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.cpp
===================================================================
--- /dev/null
+++ lib/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.cpp
@@ -0,0 +1,477 @@
+//==-- StackUsageMeasuringVisitor.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 the StackUsageMeasuringVisitor, a RecursiveASTVisitor
+// based class for summarizing the stack usage of statement trees.
+// It can calculate the complete usage of a tree or only a subtree up to
+// the point where the given predicate becomes true.
+//
+//===----------------------------------------------------------------------===//
+
+#include <clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h>
+
+namespace clang {
+namespace stack {
+
+const Usage Usage::Empty = {0, 0, false, false};
+const Usage Usage::EmptyFlagged = {0, 0, false, true};
+
+Usage &Usage::operator+=(const Usage &U) {
+ if (ExitFlag)
+ return *this;
+ Maximal = std::max(Maximal, Constant + U.Maximal);
+ Constant += U.Constant;
+ DynAlloc = DynAlloc || U.DynAlloc;
+ ExitFlag = ExitFlag || U.ExitFlag;
+ return *this;
+}
+
+namespace {
+
+Usage withoutConstant(Usage U) {
+ return {0, U.Maximal, U.DynAlloc, U.ExitFlag};
+}
+
+bool countsAsZero(const Expr *Ex) {
+ auto Cls = Ex->getStmtClass();
+ return Cls == Stmt::StmtClass::DeclRefExprClass ||
+ Cls == Stmt::StmtClass::MemberExprClass ||
+ Cls == Stmt::StmtClass::CharacterLiteralClass ||
+ Cls == Stmt::StmtClass::CXXBoolLiteralExprClass ||
+ Cls == Stmt::StmtClass::CXXNullPtrLiteralExprClass ||
+ Cls == Stmt::StmtClass::FloatingLiteralClass ||
+ Cls == Stmt::StmtClass::ImaginaryLiteralClass ||
+ Cls == Stmt::StmtClass::IntegerLiteralClass ||
+ Cls == Stmt::StmtClass::StringLiteralClass;
+}
+
+bool isTypeDependent(const Stmt *S) {
+ if (const auto *E = dyn_cast<Expr>(S)) {
+ return E->isTypeDependent();
+ }
+ return false;
+}
+}
+
+void StackUsageMeasuringVisitor::putUsage(const Stmt *S, Usage U) {
+ if (U.ExitFlag) {
+ ExitFlag = true;
+ ContinueTraversing = !HardExit;
+ }
+ StmtSubtreeUsages[S] = U;
+}
+
+Usage StackUsageMeasuringVisitor::retrieveUsage(const Stmt *S) const {
+ if (S == nullptr)
+ return Usage::Empty;
+ auto Iter = StmtSubtreeUsages.find(S);
+ if (Iter != StmtSubtreeUsages.end()) {
+ Usage U = Iter->second;
+ return U;
+ } else {
+ return Usage::Empty;
+ }
+}
+
+void StackUsageMeasuringVisitor::clear() {
+ StmtSubtreeUsages.clear();
+ DeclSubtreeUsages.clear();
+ ExitFlag = false;
+ ContinueTraversing = true;
+}
+
+void StackUsageMeasuringVisitor::putUsage(const Decl *D, Usage U) {
+ if (U.ExitFlag) {
+ ExitFlag = true;
+ ContinueTraversing = !HardExit;
+ }
+ DeclSubtreeUsages[D] = U;
+}
+
+Usage StackUsageMeasuringVisitor::retrieveUsage(const Decl *D) const {
+ if (D == nullptr)
+ return Usage::Empty;
+ auto Iter = DeclSubtreeUsages.find(D);
+ if (Iter != DeclSubtreeUsages.end()) {
+ Usage U = Iter->second;
+ return U;
+ } else {
+ return Usage::Empty;
+ }
+}
+
+int StackUsageMeasuringVisitor::exprRetSize(const Expr *E) const {
+ auto StmtCls = E->getStmtClass();
+ // If it's a NoOp expression the returned value does not use extra space.
+ // Also constructors and 'ExprWithCleanups' expressions are assumed to have
+ // no extra return space costs.
+ if (E->IgnoreParenNoopCasts(Context) != E ||
+ StmtCls == Stmt::StmtClass::ExprWithCleanupsClass ||
+ StmtCls == Stmt::StmtClass::CXXConstructExprClass) {
+ return 0;
+ }
+ return sizeInBytes(E->isLValue()
+ ? Context.getLValueReferenceType(E->getType())
+ : E->getType());
+}
+
+bool StackUsageMeasuringVisitor::VisitStmt(const Stmt *S) {
+ // This will flag the statement or expression if it is the desired one.
+ if (ExitPredicate(S)) {
+ putUsage(S, Usage::EmptyFlagged);
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitDeclStmt(const DeclStmt *D) {
+ if (!hasEmptyFlaggedUsageStored(D)) {
+ Usage Summary = Usage::Empty;
+ // Summarize the variable declarations and their initializing expressions.
+ for (const auto *Dec : D->getDeclGroup()) {
+ Usage Var = retrieveUsage(Dec);
+ Summary += Var;
+ if (Var.ExitFlag)
+ break;
+ }
+ putUsage(D, Summary);
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitVarDecl(const VarDecl *D) {
+ if (!hasEmptyFlaggedUsageStored(D)) {
+ if (D->isInvalidDecl()) {
+ // Invalid declarations count as zero.
+ putUsage(D, Usage::Empty);
+ } else if (D->getType()->isDependentType()) {
+ // A template declaration was found, signal the algorithm.
+ putUsage(D, Usage::EmptyFlagged);
+ } else {
+ int VarSize = varSize(D);
+ Usage Var = {VarSize, VarSize, D->getType()->isVariableArrayType(),
+ false};
+ Usage Init = retrieveUsage(D->getInit());
+ Init.Maximal -= VarSize * isa<ArrayType>(D->getType());
+ Var += Init;
+ putUsage(D, Var);
+ }
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitExpr(const Expr *Ex) {
+ if (!hasEmptyFlaggedUsageStored(Ex)) {
+ Usage Summary = Usage::Empty;
+ if (!countsAsZero(Ex)) {
+ for (const auto &Child : Ex->children()) {
+ // The way we summarize the subexpressions is special here,
+ // because all of the temporary objects remain until the end of the
+ // execution of the whole line.
+ Usage U = retrieveUsage(Child);
+ Summary.Constant += U.Constant;
+ Summary.Maximal += U.Maximal;
+ Summary.DynAlloc = Summary.DynAlloc || U.DynAlloc;
+ Summary.ExitFlag = Summary.ExitFlag || U.ExitFlag;
+ if (Summary.ExitFlag)
+ break;
+ }
+ Summary.Maximal += exprRetSize(Ex);
+ }
+ putUsage(Ex, Summary);
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitMaterializeTemporaryExpr(
+ const MaterializeTemporaryExpr *Ex) {
+ if (!hasEmptyFlaggedUsageStored(Ex)) {
+ // We have a temporary object whose lifetime may be extended by a constant
+ // reference.
+ auto *Temporary = Ex->GetTemporaryExpr();
+
+ Usage U = retrieveUsage(Temporary);
+ if (ForceTemporariesToConstant) {
+ // In this case, we force all the temporaries into the constant usage
+ // if they are not held by static references. This way of calculation
+ // is useful for summarizing an expression locally.
+ int Constant =
+ (Ex->getStorageDuration() != SD_Static) *
+ sizeInBytes(Temporary->IgnoreParenNoopCasts(Context)->getType());
+ U.Constant += Constant;
+ } else {
+ // Usually we count constant usage only if there is a non-static variable
+ // declaration that keeps the temporary alive.
+ int Constant =
+ (Ex->getExtendingDecl() && Ex->getStorageDuration() != SD_Static)
+ ? exprRetSize(Temporary)
+ : 0;
+ U.Constant += Constant;
+ }
+ U.Maximal = std::max(U.Maximal, U.Constant);
+ putUsage(Ex, U);
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitLambdaExpr(const LambdaExpr *Ex) {
+ if (!hasEmptyFlaggedUsageStored(Ex)) {
+ // In this case we are only interested in the result type,
+ // the body is checked as a separate function by the checker.
+ int Result = exprRetSize(Ex);
+ putUsage(Ex, {0, Result, false, false});
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitCXXThrowExpr(const CXXThrowExpr *Ex) {
+ if (!hasEmptyFlaggedUsageStored(Ex)) {
+ // We assume no 'constant' stack usage here.
+ Usage Sub = retrieveUsage(Ex->getSubExpr());
+ putUsage(Ex, {0, Sub.Maximal, Sub.DynAlloc, Sub.ExitFlag});
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitArraySubscriptExpr(
+ const ArraySubscriptExpr *Ex) {
+ if (!hasEmptyFlaggedUsageStored(Ex)) {
+ // We assume no extra usage for array elements, but the way the are reached
+ // may create extra usage.
+ Usage Base = retrieveUsage(Ex->getBase());
+ Usage Idx = retrieveUsage(Ex->getIdx());
+ putUsage(Ex, {Base.Constant + Idx.Constant, Base.Maximal + Idx.Maximal,
+ Base.DynAlloc || Idx.DynAlloc, Idx.ExitFlag});
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitCompoundStmt(const CompoundStmt *CS) {
+ if (!hasEmptyFlaggedUsageStored(CS)) {
+ // The 'Constant' usage adds up from all the children,
+ // the 'Maximal' usage is the maximum of all children values.
+ Usage Summary = Usage::Empty;
+ for (const auto *Child : CS->body()) {
+ Summary += retrieveUsage(Child);
+ if (Summary.ExitFlag)
+ break;
+ }
+ // All the compound statements except for the function body have
+ // zero constant usage. In the function body constant usage can be
+ // used for partial summaries.
+ if (CS != rootStmt)
+ Summary.Constant = 0;
+ putUsage(CS, Summary);
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitIfStmt(const IfStmt *If) {
+ if (!hasEmptyFlaggedUsageStored(If)) {
+ // The variables declared in the condition field exist during the execution
+ // of the chosen branch, but only one of the branches get executed,
+ // so we take the maximal one and add the condition.
+ // We also have to take into account the ExitFlags of the branches, so if
+ // a branch has less usage but is flagged, it must be the one we use.
+ Usage IfUsage = retrieveUsage(If->getInit());
+ const DeclStmt *Decl = If->getConditionVariableDeclStmt();
+ IfUsage += Decl ? retrieveUsage(Decl) : retrieveUsage(If->getCond());
+
+ Usage ThenUs = retrieveUsage(If->getThen());
+ Usage ElseUs = retrieveUsage(If->getElse());
+ // We have to choose the branch that has greater maximal usage or is
+ // flagged.
+ if (ThenUs.ExitFlag ||
+ (!ElseUs.ExitFlag && ThenUs.Maximal > ElseUs.Maximal)) {
+ IfUsage += ThenUs;
+ } else {
+ IfUsage += ElseUs;
+ }
+ putUsage(If, withoutConstant(IfUsage));
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitSwitchStmt(const SwitchStmt *S) {
+ if (!hasEmptyFlaggedUsageStored(S)) {
+ // The the condition variable is handled like in the if statement,
+ // the body is treated as one big compound statement,
+ // since we are mainly interested in the maximal usage and declarations
+ // can't be case specific or they exist in substatements,
+ // where they go into the maximal usage.
+ Usage SwitchUsage = retrieveUsage(S->getInit());
+ const DeclStmt *Decl = S->getConditionVariableDeclStmt();
+
+ SwitchUsage += Decl ? retrieveUsage(Decl) : retrieveUsage(S->getCond());
+ SwitchUsage += retrieveUsage(S->getBody());
+
+ putUsage(S, withoutConstant(SwitchUsage));
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitForStmt(const ForStmt *For) { // TODO
+ if (!hasEmptyFlaggedUsageStored(For)) {
+ // From the head only the loop variable exists during the execution of the
+ // body, but the subexpressions in the condition and the increment fields
+ // may affect the maximal usage.
+ Usage ForUsage = retrieveUsage(For->getInit());
+
+ const DeclStmt *Decl = For->getConditionVariableDeclStmt();
+ ForUsage += Decl ? retrieveUsage(Decl) : retrieveUsage(For->getCond());
+ ForUsage += retrieveUsage(For->getInc());
+ ForUsage += retrieveUsage(For->getBody());
+
+ putUsage(For, withoutConstant(ForUsage));
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitCXXForRangeStmt(
+ const CXXForRangeStmt *For) {
+ if (!hasEmptyFlaggedUsageStored(For)) {
+ // Similar logic to the for statement, every hidden declaration is
+ // taken into account.
+ Usage ForRangeUsage = retrieveUsage(For->getLoopVarStmt());
+ ForRangeUsage += retrieveUsage(For->getBeginStmt());
+ ForRangeUsage += retrieveUsage(For->getEndStmt());
+ ForRangeUsage += retrieveUsage(For->getBody());
+ ForRangeUsage += retrieveUsage(For->getInc());
+ ForRangeUsage += retrieveUsage(For->getRangeStmt());
+
+ putUsage(For, withoutConstant(ForRangeUsage));
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitWhileStmt(const WhileStmt *While) {
+ if (!hasEmptyFlaggedUsageStored(While)) {
+ // Similar logic to the for statement, head and body handled according to
+ // lifetime rules.
+ Usage WhileUsage = retrieveUsage(While->getCond());
+ WhileUsage += retrieveUsage(While->getBody());
+
+ putUsage(While, withoutConstant(WhileUsage));
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitDoStmt(const DoStmt *DoWhile) {
+ if (!hasEmptyFlaggedUsageStored(DoWhile)) {
+ // Similar logic to the while statment, but taking into account that
+ // the lifetime of the variables in the body end before the condition
+ Usage DoWhileUsage = withoutConstant(retrieveUsage(DoWhile->getBody()));
+ DoWhileUsage += withoutConstant(retrieveUsage(DoWhile->getCond()));
+ putUsage(DoWhile, DoWhileUsage);
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitCXXTryStmt(const CXXTryStmt *Try) {
+ if (!hasEmptyFlaggedUsageStored(Try)) {
+ // The maximal usage is calculated between try and except blocks.
+ // Try block allocations are assumed to be cleared before the execution of
+ // any handlers.
+
+ // Function bodies can be try statements. If this is the body, it needs
+ // constant usage statistic in case we do a partial summary.
+ bool isRootStmt = rootStmt == Try;
+ Usage TryUsage = isRootStmt
+ ? retrieveUsage(Try->getTryBlock())
+ : withoutConstant(retrieveUsage(Try->getTryBlock()));
+
+ for (unsigned i = 0; i < Try->getNumHandlers() && !TryUsage.ExitFlag; ++i) {
+ auto Dec = Try->getHandler(i)->getExceptionDecl();
+ int Hdecl = Dec ? varSize(Dec) : 0;
+ Usage HandlerBodyUsage =
+ isRootStmt ? retrieveUsage(Try->getHandler(i)->getHandlerBlock())
+ : withoutConstant(retrieveUsage(
+ Try->getHandler(i)->getHandlerBlock()));
+ HandlerBodyUsage.Maximal += Hdecl;
+ TryUsage += HandlerBodyUsage;
+ }
+ putUsage(Try, TryUsage);
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitReturnStmt(const ReturnStmt *Return) {
+ if (!hasEmptyFlaggedUsageStored(Return)) {
+ putUsage(Return, retrieveUsage(Return->getRetValue()));
+ }
+ return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitUnaryExprOrTypeTraitExpr(
+ const UnaryExprOrTypeTraitExpr *Ex) {
+ if (!hasEmptyFlaggedUsageStored(Ex) && Ex->getKind() == UETT_SizeOf) {
+ // The sizeof expression is special case where the children are not
+ // evaluated during execution.
+ Usage Returned = Usage::Empty;
+ Returned.Maximal = exprRetSize(Ex);
+ Returned.Constant = 0;
+ Returned.ExitFlag = retrieveUsage(Ex).ExitFlag;
+ putUsage(Ex, Returned);
+ }
+ // Other cases are handled by the generic Expr branch.
+ return ContinueTraversing;
+}
+
+Usage StackUsageMeasuringVisitor::sumStmt(const Stmt *S, Predicate ExitPred,
+ bool Hard,
+ bool ForceTempsToConstant) {
+ HardExit = Hard;
+ ForceTemporariesToConstant = ForceTempsToConstant;
+ clear();
+ ExitPredicate = ExitPred;
+ TraverseStmt(const_cast<Stmt *>(S));
+ auto U = hasUsageStored(S) ? retrieveUsage(S) : Usage::EmptyFlagged;
+ return U;
+}
+
+Usage StackUsageMeasuringVisitor::calculateFunctionUsage(
+ const FunctionDecl *Func, Predicate ExitPred, bool Hard) {
+ if (!Func ||
+ Func->getTemplatedKind() != FunctionDecl::TemplatedKind::TK_NonTemplate ||
+ Func->isPure() || !Func->hasBody())
+ return Usage::EmptyFlagged;
+ int SizeCounter = 0;
+ for (const auto *Param : Func->parameters()) {
+ // It is no use calculating usage on templates.
+ if (Param->getType()->isDependentType())
+ return Usage::EmptyFlagged;
+ int ParamSize = sizeInBytes(Param->getType());
+ SizeCounter += ParamSize;
+ }
+ // then check the body.
+ auto *Body = Func->getBody();
+ rootStmt = Body;
+ Usage Us = sumStmt(Body, ExitPred, Hard, false);
+ Us.Maximal += SizeCounter;
+ Us.Constant += SizeCounter;
+ return Us;
+}
+
+Usage StackUsageMeasuringVisitor::sumFunctionUpUntil(const FunctionDecl *Func,
+ const Stmt *Particular) {
+ return calculateFunctionUsage(
+ Func, [Particular](const Stmt *S) { return S == Particular; }, false);
+}
+
+Usage StackUsageMeasuringVisitor::sumFunctionUpUntilTemplate(
+ const FunctionDecl *Func) {
+ return calculateFunctionUsage(Func, isTypeDependent, true);
+}
+
+Usage StackUsageMeasuringVisitor::sumStmtWithTemporariesExtracted(
+ const Stmt *S) {
+ return sumStmt(S, isTypeDependent, false, true);
+}
+
+} // stack
+} // clang
Index: lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp
===================================================================
--- /dev/null
+++ lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp
@@ -0,0 +1,159 @@
+//=======- StackSizeChecker.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 a checker that checks for suspiciously high stack use.
+// The checker produces a warning whenever the given stack limit is exceeded.
+// The limit is defined by the "StackUsageLimit" analyzer parameter,
+// or defaults to 100000 bytes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/AST/StmtCXX.h"
+#include "clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h"
+#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include <sstream>
+
+using namespace clang;
+using namespace clang::ento;
+
+namespace {
+
+struct StackInt {
+ int Used;
+ bool operator==(const StackInt &Other) const { return Used == Other.Used; }
+ void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Used); }
+ operator int() const { return Used; }
+};
+
+class StackSizeChecker
+ : public Checker<check::PreCall, check::PostCall, check::EndFunction> {
+ mutable std::unique_ptr<BugType> StackOverflowBugType;
+
+ void generateError(int NumBytes, SourceRange Range, CheckerContext &C) const;
+
+public:
+ StackSizeChecker() : StackUsageLimit(0) {}
+ int StackUsageLimit;
+
+ void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+ void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+ void checkEndFunction(CheckerContext &C) const;
+};
+
+int countPredecessors(const CheckerContext &C) {
+ const auto *Frame = C.getStackFrame()->getParent();
+ int N = 0;
+ while (Frame) {
+ const auto *D = dyn_cast_or_null<FunctionDecl>(Frame->getDecl());
+ if (D)
+ ++N;
+ else
+ break;
+ Frame = dyn_cast_or_null<StackFrameContext>(Frame->getParent());
+ }
+ return N;
+}
+
+int length(const llvm::ImmutableList<StackInt>& L) {
+ int N = 0;
+ auto I = L.begin();
+ auto E = L.end();
+ while(I != E){
+ ++N;
+ ++I;
+ }
+ return N;
+}
+}
+
+REGISTER_LIST_WITH_PROGRAMSTATE(StackSizeList, StackInt)
+
+void StackSizeChecker::generateError(int NumBytes, SourceRange Range,
+ CheckerContext &C) const {
+ ExplodedNode *ErrNode = C.generateNonFatalErrorNode();
+ // If we've already reached this node on another path, return.
+ if (!ErrNode)
+ return;
+
+ if (!StackOverflowBugType) {
+ StackOverflowBugType.reset(
+ new BugType(this, "Stack overuse", "Program error"));
+ }
+ // Generate the report.
+ std::ostringstream ErrorMessage;
+ ErrorMessage << "Estimated stack usage is " << NumBytes << " bytes";
+ auto R = llvm::make_unique<BugReport>(*StackOverflowBugType,
+ ErrorMessage.str(), ErrNode);
+ R->addRange(Range);
+ C.emitReport(std::move(R));
+}
+
+void StackSizeChecker::checkEndFunction(CheckerContext &C) const {
+ ProgramStateRef State = C.getState();
+ auto StackLevels = State->get<StackSizeList>();
+ if (length(StackLevels) != countPredecessors(C))
+ return;
+ stack::StackUsageMeasuringVisitor Visitor(C.getASTContext());
+ auto Declaration =
+ dyn_cast_or_null<FunctionDecl>(C.getLocationContext()->getDecl());
+ int NumBytes =
+ Visitor
+ .sumFunctionUpUntilTemplate(const_cast<FunctionDecl *>(Declaration))
+ .Maximal;
+ if (!StackLevels.isEmpty())
+ NumBytes += StackLevels.getHead();
+
+ if (NumBytes > StackUsageLimit)
+ generateError(NumBytes, Declaration->getSourceRange(), C);
+}
+
+void StackSizeChecker::checkPreCall(const CallEvent &Call,
+ CheckerContext &C) const {
+ ProgramStateRef State = C.getState();
+ auto StackLevels = State->get<StackSizeList>();
+ if (length(StackLevels) != countPredecessors(C))
+ return;
+
+ stack::StackUsageMeasuringVisitor Visitor(C.getASTContext());
+
+ auto *Declaration =
+ dyn_cast_or_null<FunctionDecl>(C.getLocationContext()->getDecl());
+ int NumBytes =
+ Visitor.sumFunctionUpUntil(Declaration, Call.getOriginExpr()).Constant +
+ Visitor.sumStmtWithTemporariesExtracted(Call.getOriginExpr()).Constant;
+ if (!StackLevels.isEmpty())
+ NumBytes += StackLevels.getHead();
+
+ if (NumBytes > StackUsageLimit) {
+ generateError(NumBytes, Call.getSourceRange(), C);
+ }
+ State = State->add<StackSizeList>({NumBytes});
+ C.addTransition(State);
+}
+
+void StackSizeChecker::checkPostCall(const CallEvent &Call,
+ CheckerContext &C) const {
+ ProgramStateRef State = C.getState();
+ auto StackLevels = State->get<StackSizeList>();
+ if (length(StackLevels) != countPredecessors(C) + 1)
+ return;
+ State = State->set<StackSizeList>(StackLevels.getTail());
+ C.addTransition(State);
+}
+
+void clang::ento::registerStackSizeChecker(CheckerManager &Mgr) {
+ StackSizeChecker *Check = Mgr.registerChecker<StackSizeChecker>();
+ Check->StackUsageLimit = Mgr.getAnalyzerOptions().getOptionAsInteger(
+ "StackUsageLimit", 100000, Check);
+}
Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt
===================================================================
--- lib/StaticAnalyzer/Checkers/CMakeLists.txt
+++ lib/StaticAnalyzer/Checkers/CMakeLists.txt
@@ -83,6 +83,7 @@
RunLoopAutoreleaseLeakChecker.cpp
SimpleStreamChecker.cpp
StackAddrEscapeChecker.cpp
+ StackSizeChecker.cpp
StdLibraryFunctionsChecker.cpp
StreamChecker.cpp
TaintTesterChecker.cpp
Index: include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h
===================================================================
--- /dev/null
+++ include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h
@@ -0,0 +1,144 @@
+//==-- StackUsageMeasuringVisitor.h -------------------------------*- C++ -*--//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file declares the StackUsageMeasuringVisitor, a RecursiveASTVisitor
+// based class for summarizing the stack usage of statement trees.
+// It can calculate the complete usage of a tree or only a subtree up to
+// the point where the given predicate becomes true.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/DenseMap.h"
+
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/FrontendAction.h"
+#include "clang/Tooling/Tooling.h"
+#include <functional>
+#include <map>
+
+namespace clang {
+namespace stack {
+
+struct Usage {
+
+ Usage &operator+=(const Usage &U);
+
+ bool operator==(const Usage &U) const {
+ return Constant == U.Constant && Maximal == U.Maximal &&
+ DynAlloc == U.DynAlloc && ExitFlag == U.ExitFlag;
+ }
+
+ int Constant; // The amount of used space that survives the statement,
+ // important for variable declarations and temporaries extended
+ // by const references.
+ int Maximal; // Greater or equal to 'Constant', includes temporaries created
+ // by the statement.
+ bool DynAlloc; // Flag for dynamic stack allocation in the statement or any of
+ // its children.
+ bool ExitFlag; // Tells the visitor to cease consuming the tree.
+
+ static const Usage Empty, EmptyFlagged;
+};
+
+class StackUsageMeasuringVisitor
+ : public clang::RecursiveASTVisitor<StackUsageMeasuringVisitor> {
+
+public:
+ using Predicate = std::function<bool(const Stmt *)>;
+
+ explicit StackUsageMeasuringVisitor(ASTContext &Context)
+ : Context(Context), ContinueTraversing(true), ExitFlag(false),
+ HardExit(false), ForceTemporariesToConstant(false),
+ ExitPredicate(nullptr) {}
+
+ Usage collected() const;
+
+ // The visitor should traver post-order, because each node needs
+ // precalculated information in their children.
+ bool shouldTraversePostOrder() const { return true; }
+
+ bool VisitStmt(const Stmt *);
+
+ bool VisitDeclStmt(const DeclStmt *);
+ bool VisitExpr(const Expr *);
+ bool VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *);
+ bool VisitLambdaExpr(const LambdaExpr *);
+ bool VisitCXXThrowExpr(const CXXThrowExpr *);
+ bool VisitArraySubscriptExpr(const ArraySubscriptExpr *);
+ bool VisitCompoundStmt(const CompoundStmt *);
+ bool VisitIfStmt(const IfStmt *);
+ bool VisitSwitchStmt(const SwitchStmt *);
+ bool VisitForStmt(const ForStmt *);
+ bool VisitCXXForRangeStmt(const CXXForRangeStmt *);
+ bool VisitWhileStmt(const WhileStmt *);
+ bool VisitDoStmt(const DoStmt *);
+ bool VisitCXXTryStmt(const CXXTryStmt *);
+ bool VisitReturnStmt(const ReturnStmt *);
+ bool VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *);
+ bool VisitVarDecl(const VarDecl *);
+
+ Usage calculateFunctionUsage(const FunctionDecl *, Predicate, bool);
+ Usage sumFunctionUpUntil(const FunctionDecl *, const Stmt *);
+ Usage sumFunctionUpUntilTemplate(const FunctionDecl *);
+ Usage sumStmtWithTemporariesExtracted(const Stmt *);
+ Usage sumStmt(const Stmt *, Predicate, bool, bool);
+private:
+ void clear();
+ bool hasUsageStored(const Stmt *S) const {
+ return StmtSubtreeUsages.find(S) != StmtSubtreeUsages.end();
+ }
+ bool hasUsageStored(const Decl *D) const {
+ return DeclSubtreeUsages.find(D) != DeclSubtreeUsages.end();
+ }
+
+ bool hasEmptyFlaggedUsageStored(const Stmt *S) const {
+ auto iter = StmtSubtreeUsages.find(S);
+ return iter != StmtSubtreeUsages.end() &&
+ iter->second == Usage::EmptyFlagged;
+ }
+ bool hasEmptyFlaggedUsageStored(const Decl *D) const {
+ auto iter = DeclSubtreeUsages.find(D);
+ return iter != DeclSubtreeUsages.end() &&
+ iter->second == Usage::EmptyFlagged;
+ }
+ void putUsage(const Stmt *, Usage);
+ Usage retrieveUsage(const Stmt *) const;
+ void putUsage(const Decl *, Usage);
+ Usage retrieveUsage(const Decl *) const;
+
+ int varSize(const VarDecl *Var) const {
+ return Var->hasLocalStorage() * sizeInBytes(Var->getType());
+ }
+
+ int sizeInBytes(QualType T) const {
+ return T->isIncompleteType() || T->isPlaceholderType()
+ ? 0
+ : Context.getTypeSize(T) / Context.getCharWidth();
+ }
+ int exprRetSize(const Expr *) const;
+
+ ASTContext &Context;
+
+ llvm::DenseMap<const Stmt *, Usage> StmtSubtreeUsages;
+ llvm::DenseMap<const Decl *, Usage> DeclSubtreeUsages;
+
+ Stmt* rootStmt;
+
+ bool ContinueTraversing;
+ bool ExitFlag;
+ bool HardExit;
+ bool ForceTemporariesToConstant;
+
+ Predicate ExitPredicate;
+};
+
+} // stack
+} // clang
Index: include/clang/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -140,6 +140,10 @@
let ParentPackage = CoreAlpha in {
+def StackSizeChecker : Checker<"StackSize">,
+ HelpText<"Warn if estimated stack usage exceeds the StackUsageLimit parameter (measured in bytes, defaults to 100000)">,
+ DescFile<"StackSizeChecker.cpp">;
+
def BoolAssignmentChecker : Checker<"BoolAssignment">,
HelpText<"Warn about assigning non-{0,1} values to Boolean variables">,
DescFile<"BoolAssignmentChecker.cpp">;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
