aboutsummaryrefslogtreecommitdiff
path: root/clang/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'clang/lib/Analysis')
-rw-r--r--clang/lib/Analysis/FlowSensitive/CMakeLists.txt1
-rw-r--r--clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp79
-rw-r--r--clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp6
-rw-r--r--clang/lib/Analysis/FlowSensitive/FormulaSerialization.cpp153
-rw-r--r--clang/lib/Analysis/LifetimeSafety.cpp308
-rw-r--r--clang/lib/Analysis/ThreadSafety.cpp4
-rw-r--r--clang/lib/Analysis/ThreadSafetyCommon.cpp4
-rw-r--r--clang/lib/Analysis/UnsafeBufferUsage.cpp22
8 files changed, 507 insertions, 70 deletions
diff --git a/clang/lib/Analysis/FlowSensitive/CMakeLists.txt b/clang/lib/Analysis/FlowSensitive/CMakeLists.txt
index 0c30df8..97e09c9 100644
--- a/clang/lib/Analysis/FlowSensitive/CMakeLists.txt
+++ b/clang/lib/Analysis/FlowSensitive/CMakeLists.txt
@@ -6,6 +6,7 @@ add_clang_library(clangAnalysisFlowSensitive
DataflowAnalysisContext.cpp
DataflowEnvironment.cpp
Formula.cpp
+ FormulaSerialization.cpp
HTMLLogger.cpp
Logger.cpp
RecordOps.cpp
diff --git a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp
index 6421ad3..06a8878 100644
--- a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp
+++ b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp
@@ -208,6 +208,24 @@ bool DataflowAnalysisContext::equivalentFormulas(const Formula &Val1,
return isUnsatisfiable(std::move(Constraints));
}
+llvm::DenseSet<Atom> DataflowAnalysisContext::collectDependencies(
+ llvm::DenseSet<Atom> Tokens) const {
+ // Use a worklist algorithm, with `Remaining` holding the worklist and
+ // `Tokens` tracking which atoms have already been added to the worklist.
+ std::vector<Atom> Remaining(Tokens.begin(), Tokens.end());
+ while (!Remaining.empty()) {
+ Atom CurrentToken = Remaining.back();
+ Remaining.pop_back();
+ if (auto DepsIt = FlowConditionDeps.find(CurrentToken);
+ DepsIt != FlowConditionDeps.end())
+ for (Atom A : DepsIt->second)
+ if (Tokens.insert(A).second)
+ Remaining.push_back(A);
+ }
+
+ return Tokens;
+}
+
void DataflowAnalysisContext::addTransitiveFlowConditionConstraints(
Atom Token, llvm::SetVector<const Formula *> &Constraints) {
llvm::DenseSet<Atom> AddedTokens;
@@ -224,6 +242,8 @@ void DataflowAnalysisContext::addTransitiveFlowConditionConstraints(
auto ConstraintsIt = FlowConditionConstraints.find(Token);
if (ConstraintsIt == FlowConditionConstraints.end()) {
+ // The flow condition is unconstrained. Just add the atom directly, which
+ // is equivalent to asserting it is true.
Constraints.insert(&arena().makeAtomRef(Token));
} else {
// Bind flow condition token via `iff` to its set of constraints:
@@ -239,6 +259,65 @@ void DataflowAnalysisContext::addTransitiveFlowConditionConstraints(
}
}
+static void getReferencedAtoms(const Formula &F,
+ llvm::DenseSet<dataflow::Atom> &Refs) {
+ switch (F.kind()) {
+ case Formula::AtomRef:
+ Refs.insert(F.getAtom());
+ break;
+ case Formula::Literal:
+ break;
+ case Formula::Not:
+ getReferencedAtoms(*F.operands()[0], Refs);
+ break;
+ case Formula::And:
+ case Formula::Or:
+ case Formula::Implies:
+ case Formula::Equal:
+ ArrayRef<const Formula *> Operands = F.operands();
+ getReferencedAtoms(*Operands[0], Refs);
+ getReferencedAtoms(*Operands[1], Refs);
+ break;
+ }
+}
+
+SimpleLogicalContext DataflowAnalysisContext::exportLogicalContext(
+ llvm::DenseSet<dataflow::Atom> TargetTokens) const {
+ SimpleLogicalContext LC;
+
+ if (Invariant != nullptr) {
+ LC.Invariant = Invariant;
+ getReferencedAtoms(*Invariant, TargetTokens);
+ }
+
+ llvm::DenseSet<dataflow::Atom> Dependencies =
+ collectDependencies(std::move(TargetTokens));
+
+ for (dataflow::Atom Token : Dependencies) {
+ // Only process the token if it is constrained. Unconstrained tokens don't
+ // have dependencies.
+ const Formula *Constraints = FlowConditionConstraints.lookup(Token);
+ if (Constraints == nullptr)
+ continue;
+ LC.TokenDefs[Token] = Constraints;
+
+ if (auto DepsIt = FlowConditionDeps.find(Token);
+ DepsIt != FlowConditionDeps.end())
+ LC.TokenDeps[Token] = DepsIt->second;
+ }
+
+ return LC;
+}
+
+void DataflowAnalysisContext::initLogicalContext(SimpleLogicalContext LC) {
+ Invariant = LC.Invariant;
+ FlowConditionConstraints = std::move(LC.TokenDefs);
+ // TODO: The dependencies in `LC.TokenDeps` can be reconstructed from
+ // `LC.TokenDefs`. Give the caller the option to reconstruct, rather than
+ // providing them directly, to save caller space (memory/disk).
+ FlowConditionDeps = std::move(LC.TokenDeps);
+}
+
static void printAtomList(const llvm::SmallVector<Atom> &Atoms,
llvm::raw_ostream &OS) {
OS << "(";
diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
index 256ea182..f14cb43 100644
--- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -532,9 +532,11 @@ void Environment::initialize() {
} else if (auto *FieldBeingInitialized =
dyn_cast<FieldDecl>(Parent->getLambdaContextDecl())) {
// This is in a field initializer, rather than a method.
+ const RecordDecl *RD = FieldBeingInitialized->getParent();
+ const ASTContext &Ctx = RD->getASTContext();
+ CanQualType T = Ctx.getCanonicalTagType(RD);
setThisPointeeStorageLocation(
- cast<RecordStorageLocation>(createObject(QualType(
- FieldBeingInitialized->getParent()->getTypeForDecl(), 0))));
+ cast<RecordStorageLocation>(createObject(T)));
} else {
assert(false && "Unexpected this-capturing lambda context.");
}
diff --git a/clang/lib/Analysis/FlowSensitive/FormulaSerialization.cpp b/clang/lib/Analysis/FlowSensitive/FormulaSerialization.cpp
new file mode 100644
index 0000000..df15a1d
--- /dev/null
+++ b/clang/lib/Analysis/FlowSensitive/FormulaSerialization.cpp
@@ -0,0 +1,153 @@
+//===- FormulaSerialization.cpp ---------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/FlowSensitive/FormulaSerialization.h"
+#include "clang/Analysis/FlowSensitive/Arena.h"
+#include "clang/Analysis/FlowSensitive/Formula.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <cassert>
+
+namespace clang::dataflow {
+
+// Returns the leading indicator of operation formulas. `AtomRef` and `Literal`
+// are handled differently.
+static char compactSigil(Formula::Kind K) {
+ switch (K) {
+ case Formula::AtomRef:
+ case Formula::Literal:
+ // No sigil.
+ return '\0';
+ case Formula::Not:
+ return '!';
+ case Formula::And:
+ return '&';
+ case Formula::Or:
+ return '|';
+ case Formula::Implies:
+ return '>';
+ case Formula::Equal:
+ return '=';
+ }
+ llvm_unreachable("unhandled formula kind");
+}
+
+void serializeFormula(const Formula &F, llvm::raw_ostream &OS) {
+ switch (Formula::numOperands(F.kind())) {
+ case 0:
+ switch (F.kind()) {
+ case Formula::AtomRef:
+ OS << F.getAtom();
+ break;
+ case Formula::Literal:
+ OS << (F.literal() ? 'T' : 'F');
+ break;
+ default:
+ llvm_unreachable("unhandled formula kind");
+ }
+ break;
+ case 1:
+ OS << compactSigil(F.kind());
+ serializeFormula(*F.operands()[0], OS);
+ break;
+ case 2:
+ OS << compactSigil(F.kind());
+ serializeFormula(*F.operands()[0], OS);
+ serializeFormula(*F.operands()[1], OS);
+ break;
+ default:
+ llvm_unreachable("unhandled formula arity");
+ }
+}
+
+static llvm::Expected<const Formula *>
+parsePrefix(llvm::StringRef &Str, Arena &A,
+ llvm::DenseMap<unsigned, Atom> &AtomMap) {
+ if (Str.empty())
+ return llvm::createStringError(llvm::inconvertibleErrorCode(),
+ "unexpected end of input");
+
+ char Prefix = Str[0];
+ Str = Str.drop_front();
+
+ switch (Prefix) {
+ case 'T':
+ return &A.makeLiteral(true);
+ case 'F':
+ return &A.makeLiteral(false);
+ case 'V': {
+ unsigned AtomID;
+ if (Str.consumeInteger(10, AtomID))
+ return llvm::createStringError(llvm::inconvertibleErrorCode(),
+ "expected atom id");
+ auto [It, Inserted] = AtomMap.try_emplace(AtomID, Atom());
+ if (Inserted)
+ It->second = A.makeAtom();
+ return &A.makeAtomRef(It->second);
+ }
+ case '!': {
+ auto OperandOrErr = parsePrefix(Str, A, AtomMap);
+ if (!OperandOrErr)
+ return OperandOrErr.takeError();
+ return &A.makeNot(**OperandOrErr);
+ }
+ case '&':
+ case '|':
+ case '>':
+ case '=': {
+ auto LeftOrErr = parsePrefix(Str, A, AtomMap);
+ if (!LeftOrErr)
+ return LeftOrErr.takeError();
+
+ auto RightOrErr = parsePrefix(Str, A, AtomMap);
+ if (!RightOrErr)
+ return RightOrErr.takeError();
+
+ const Formula &LHS = **LeftOrErr;
+ const Formula &RHS = **RightOrErr;
+
+ switch (Prefix) {
+ case '&':
+ return &A.makeAnd(LHS, RHS);
+ case '|':
+ return &A.makeOr(LHS, RHS);
+ case '>':
+ return &A.makeImplies(LHS, RHS);
+ case '=':
+ return &A.makeEquals(LHS, RHS);
+ default:
+ llvm_unreachable("unexpected binary op");
+ }
+ }
+ default:
+ return llvm::createStringError(llvm::inconvertibleErrorCode(),
+ "unexpected prefix character: %c", Prefix);
+ }
+}
+
+llvm::Expected<const Formula *>
+parseFormula(llvm::StringRef Str, Arena &A,
+ llvm::DenseMap<unsigned, Atom> &AtomMap) {
+ size_t OriginalSize = Str.size();
+ llvm::Expected<const Formula *> F = parsePrefix(Str, A, AtomMap);
+ if (!F)
+ return F.takeError();
+ if (!Str.empty())
+ return llvm::createStringError(llvm::inconvertibleErrorCode(),
+ ("unexpected suffix of length: " +
+ llvm::Twine(Str.size() - OriginalSize))
+ .str());
+ return F;
+}
+
+} // namespace clang::dataflow
diff --git a/clang/lib/Analysis/LifetimeSafety.cpp b/clang/lib/Analysis/LifetimeSafety.cpp
index f39998c..c2e6dd74 100644
--- a/clang/lib/Analysis/LifetimeSafety.cpp
+++ b/clang/lib/Analysis/LifetimeSafety.cpp
@@ -45,10 +45,11 @@ struct Loan {
/// is represented as empty LoanSet
LoanID ID;
AccessPath Path;
- SourceLocation IssueLoc;
+ /// The expression that creates the loan, e.g., &x.
+ const Expr *IssueExpr;
- Loan(LoanID id, AccessPath path, SourceLocation loc)
- : ID(id), Path(path), IssueLoc(loc) {}
+ Loan(LoanID id, AccessPath path, const Expr *IssueExpr)
+ : ID(id), Path(path), IssueExpr(IssueExpr) {}
};
/// An Origin is a symbolic identifier that represents the set of possible
@@ -82,8 +83,8 @@ class LoanManager {
public:
LoanManager() = default;
- Loan &addLoan(AccessPath Path, SourceLocation Loc) {
- AllLoans.emplace_back(getNextLoanID(), Path, Loc);
+ Loan &addLoan(AccessPath Path, const Expr *IssueExpr) {
+ AllLoans.emplace_back(getNextLoanID(), Path, IssueExpr);
return AllLoans.back();
}
@@ -174,6 +175,18 @@ public:
return NewID;
}
+ void dump(OriginID OID, llvm::raw_ostream &OS) const {
+ OS << OID << " (";
+ Origin O = getOrigin(OID);
+ if (const ValueDecl *VD = O.getDecl())
+ OS << "Decl: " << VD->getNameAsString();
+ else if (const Expr *E = O.getExpr())
+ OS << "Expr: " << E->getStmtClassName();
+ else
+ OS << "Unknown";
+ OS << ")";
+ }
+
private:
OriginID getNextOriginID() { return NextOriginID++; }
@@ -199,6 +212,8 @@ public:
AssignOrigin,
/// An origin escapes the function by flowing into the return value.
ReturnOfOrigin,
+ /// An origin is used (eg. dereferencing a pointer).
+ Use,
/// A marker for a specific point in the code, for testing.
TestPoint,
};
@@ -219,7 +234,7 @@ public:
return nullptr;
}
- virtual void dump(llvm::raw_ostream &OS) const {
+ virtual void dump(llvm::raw_ostream &OS, const OriginManager &) const {
OS << "Fact (Kind: " << static_cast<int>(K) << ")\n";
}
};
@@ -234,21 +249,27 @@ public:
IssueFact(LoanID LID, OriginID OID) : Fact(Kind::Issue), LID(LID), OID(OID) {}
LoanID getLoanID() const { return LID; }
OriginID getOriginID() const { return OID; }
- void dump(llvm::raw_ostream &OS) const override {
- OS << "Issue (LoanID: " << getLoanID() << ", OriginID: " << getOriginID()
- << ")\n";
+ void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override {
+ OS << "Issue (LoanID: " << getLoanID() << ", ToOrigin: ";
+ OM.dump(getOriginID(), OS);
+ OS << ")\n";
}
};
class ExpireFact : public Fact {
LoanID LID;
+ SourceLocation ExpiryLoc;
public:
static bool classof(const Fact *F) { return F->getKind() == Kind::Expire; }
- ExpireFact(LoanID LID) : Fact(Kind::Expire), LID(LID) {}
+ ExpireFact(LoanID LID, SourceLocation ExpiryLoc)
+ : Fact(Kind::Expire), LID(LID), ExpiryLoc(ExpiryLoc) {}
+
LoanID getLoanID() const { return LID; }
- void dump(llvm::raw_ostream &OS) const override {
+ SourceLocation getExpiryLoc() const { return ExpiryLoc; }
+
+ void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override {
OS << "Expire (LoanID: " << getLoanID() << ")\n";
}
};
@@ -266,9 +287,12 @@ public:
: Fact(Kind::AssignOrigin), OIDDest(OIDDest), OIDSrc(OIDSrc) {}
OriginID getDestOriginID() const { return OIDDest; }
OriginID getSrcOriginID() const { return OIDSrc; }
- void dump(llvm::raw_ostream &OS) const override {
- OS << "AssignOrigin (DestID: " << getDestOriginID()
- << ", SrcID: " << getSrcOriginID() << ")\n";
+ void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override {
+ OS << "AssignOrigin (Dest: ";
+ OM.dump(getDestOriginID(), OS);
+ OS << ", Src: ";
+ OM.dump(getSrcOriginID(), OS);
+ OS << ")\n";
}
};
@@ -282,8 +306,30 @@ public:
ReturnOfOriginFact(OriginID OID) : Fact(Kind::ReturnOfOrigin), OID(OID) {}
OriginID getReturnedOriginID() const { return OID; }
- void dump(llvm::raw_ostream &OS) const override {
- OS << "ReturnOfOrigin (OriginID: " << getReturnedOriginID() << ")\n";
+ void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override {
+ OS << "ReturnOfOrigin (";
+ OM.dump(getReturnedOriginID(), OS);
+ OS << ")\n";
+ }
+};
+
+class UseFact : public Fact {
+ OriginID UsedOrigin;
+ const Expr *UseExpr;
+
+public:
+ static bool classof(const Fact *F) { return F->getKind() == Kind::Use; }
+
+ UseFact(OriginID UsedOrigin, const Expr *UseExpr)
+ : Fact(Kind::Use), UsedOrigin(UsedOrigin), UseExpr(UseExpr) {}
+
+ OriginID getUsedOrigin() const { return UsedOrigin; }
+ const Expr *getUseExpr() const { return UseExpr; }
+
+ void dump(llvm::raw_ostream &OS, const OriginManager &OM) const override {
+ OS << "Use (";
+ OM.dump(getUsedOrigin(), OS);
+ OS << ")\n";
}
};
@@ -300,7 +346,7 @@ public:
StringRef getAnnotation() const { return Annotation; }
- void dump(llvm::raw_ostream &OS) const override {
+ void dump(llvm::raw_ostream &OS, const OriginManager &) const override {
OS << "TestPoint (Annotation: \"" << getAnnotation() << "\")\n";
}
};
@@ -339,7 +385,7 @@ public:
if (It != BlockToFactsMap.end()) {
for (const Fact *F : It->second) {
llvm::dbgs() << " ";
- F->dump(llvm::dbgs());
+ F->dump(llvm::dbgs(), OriginMgr);
}
}
llvm::dbgs() << " End of Block\n";
@@ -417,13 +463,17 @@ public:
if (VD->hasLocalStorage()) {
OriginID OID = FactMgr.getOriginMgr().getOrCreate(*UO);
AccessPath AddrOfLocalVarPath(VD);
- const Loan &L = FactMgr.getLoanMgr().addLoan(AddrOfLocalVarPath,
- UO->getOperatorLoc());
+ const Loan &L =
+ FactMgr.getLoanMgr().addLoan(AddrOfLocalVarPath, UO);
CurrentBlockFacts.push_back(
FactMgr.createFact<IssueFact>(L.ID, OID));
}
}
}
+ } else if (UO->getOpcode() == UO_Deref) {
+ // This is a pointer use, like '*p'.
+ OriginID OID = FactMgr.getOriginMgr().get(*UO->getSubExpr());
+ CurrentBlockFacts.push_back(FactMgr.createFact<UseFact>(OID, UO));
}
}
@@ -492,7 +542,8 @@ private:
// Check if the loan is for a stack variable and if that variable
// is the one being destructed.
if (LoanPath.D == DestructedVD)
- CurrentBlockFacts.push_back(FactMgr.createFact<ExpireFact>(L.ID));
+ CurrentBlockFacts.push_back(FactMgr.createFact<ExpireFact>(
+ L.ID, DtorOpt.getTriggerStmt()->getEndLoc()));
}
}
@@ -618,6 +669,7 @@ public:
}
}
+protected:
Lattice getState(ProgramPoint P) const { return PerPointStates.lookup(P); }
Lattice getInState(const CFGBlock *B) const { return InStates.lookup(B); }
@@ -665,6 +717,8 @@ private:
return D->transfer(In, *F->getAs<AssignOriginFact>());
case Fact::Kind::ReturnOfOrigin:
return D->transfer(In, *F->getAs<ReturnOfOriginFact>());
+ case Fact::Kind::Use:
+ return D->transfer(In, *F->getAs<UseFact>());
case Fact::Kind::TestPoint:
return D->transfer(In, *F->getAs<TestPointFact>());
}
@@ -676,6 +730,7 @@ public:
Lattice transfer(Lattice In, const ExpireFact &) { return In; }
Lattice transfer(Lattice In, const AssignOriginFact &) { return In; }
Lattice transfer(Lattice In, const ReturnOfOriginFact &) { return In; }
+ Lattice transfer(Lattice In, const UseFact &) { return In; }
Lattice transfer(Lattice In, const TestPointFact &) { return In; }
};
@@ -693,6 +748,20 @@ static llvm::ImmutableSet<T> join(llvm::ImmutableSet<T> A,
return A;
}
+/// Checks if set A is a subset of set B.
+template <typename T>
+static bool isSubsetOf(const llvm::ImmutableSet<T> &A,
+ const llvm::ImmutableSet<T> &B) {
+ // Empty set is a subset of all sets.
+ if (A.isEmpty())
+ return true;
+
+ for (const T &Elem : A)
+ if (!B.contains(Elem))
+ return false;
+ return true;
+}
+
/// Computes the key-wise union of two ImmutableMaps.
// TODO(opt): This key-wise join is a performance bottleneck. A more
// efficient merge could be implemented using a Patricia Trie or HAMT
@@ -700,7 +769,7 @@ static llvm::ImmutableSet<T> join(llvm::ImmutableSet<T> A,
template <typename K, typename V, typename Joiner>
static llvm::ImmutableMap<K, V>
join(llvm::ImmutableMap<K, V> A, llvm::ImmutableMap<K, V> B,
- typename llvm::ImmutableMap<K, V>::Factory &F, Joiner joinValues) {
+ typename llvm::ImmutableMap<K, V>::Factory &F, Joiner JoinValues) {
if (A.getHeight() < B.getHeight())
std::swap(A, B);
@@ -710,7 +779,7 @@ join(llvm::ImmutableMap<K, V> A, llvm::ImmutableMap<K, V> B,
const K &Key = Entry.first;
const V &ValB = Entry.second;
if (const V *ValA = A.lookup(Key))
- A = F.add(A, Key, joinValues(*ValA, ValB));
+ A = F.add(A, Key, JoinValues(*ValA, ValB));
else
A = F.add(A, Key, ValB);
}
@@ -723,17 +792,14 @@ join(llvm::ImmutableMap<K, V> A, llvm::ImmutableMap<K, V> B,
// ========================================================================= //
using OriginLoanMap = llvm::ImmutableMap<OriginID, LoanSet>;
+using ExpiredLoanMap = llvm::ImmutableMap<LoanID, const ExpireFact *>;
/// An object to hold the factories for immutable collections, ensuring
/// that all created states share the same underlying memory management.
struct LifetimeFactory {
OriginLoanMap::Factory OriginMapFactory;
LoanSet::Factory LoanSetFactory;
-
- /// Creates a singleton set containing only the given loan ID.
- LoanSet createLoanSet(LoanID LID) {
- return LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID);
- }
+ ExpiredLoanMap::Factory ExpiredLoanMapFactory;
};
/// Represents the dataflow lattice for loan propagation.
@@ -774,13 +840,15 @@ struct LoanPropagationLattice {
class LoanPropagationAnalysis
: public DataflowAnalysis<LoanPropagationAnalysis, LoanPropagationLattice,
Direction::Forward> {
-
- LifetimeFactory &Factory;
+ OriginLoanMap::Factory &OriginLoanMapFactory;
+ LoanSet::Factory &LoanSetFactory;
public:
LoanPropagationAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
- LifetimeFactory &Factory)
- : DataflowAnalysis(C, AC, F), Factory(Factory) {}
+ LifetimeFactory &LFactory)
+ : DataflowAnalysis(C, AC, F),
+ OriginLoanMapFactory(LFactory.OriginMapFactory),
+ LoanSetFactory(LFactory.LoanSetFactory) {}
using Base::transfer;
@@ -792,9 +860,9 @@ public:
// TODO(opt): Keep the state small by removing origins which become dead.
Lattice join(Lattice A, Lattice B) {
OriginLoanMap JoinedOrigins =
- utils::join(A.Origins, B.Origins, Factory.OriginMapFactory,
- [this](LoanSet S1, LoanSet S2) {
- return utils::join(S1, S2, Factory.LoanSetFactory);
+ utils::join(A.Origins, B.Origins, OriginLoanMapFactory,
+ [&](LoanSet S1, LoanSet S2) {
+ return utils::join(S1, S2, LoanSetFactory);
});
return Lattice(JoinedOrigins);
}
@@ -803,8 +871,9 @@ public:
Lattice transfer(Lattice In, const IssueFact &F) {
OriginID OID = F.getOriginID();
LoanID LID = F.getLoanID();
- return LoanPropagationLattice(Factory.OriginMapFactory.add(
- In.Origins, OID, Factory.createLoanSet(LID)));
+ return LoanPropagationLattice(OriginLoanMapFactory.add(
+ In.Origins, OID,
+ LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID)));
}
/// The destination origin's loan set is replaced by the source's.
@@ -814,7 +883,7 @@ public:
OriginID SrcOID = F.getSrcOriginID();
LoanSet SrcLoans = getLoans(In, SrcOID);
return LoanPropagationLattice(
- Factory.OriginMapFactory.add(In.Origins, DestOID, SrcLoans));
+ OriginLoanMapFactory.add(In.Origins, DestOID, SrcLoans));
}
LoanSet getLoans(OriginID OID, ProgramPoint P) {
@@ -825,7 +894,7 @@ private:
LoanSet getLoans(Lattice L, OriginID OID) {
if (auto *Loans = L.Origins.lookup(OID))
return *Loans;
- return Factory.LoanSetFactory.getEmptySet();
+ return LoanSetFactory.getEmptySet();
}
};
@@ -835,10 +904,11 @@ private:
/// The dataflow lattice for tracking the set of expired loans.
struct ExpiredLattice {
- LoanSet Expired;
+ /// Map from an expired `LoanID` to the `ExpireFact` that made it expire.
+ ExpiredLoanMap Expired;
ExpiredLattice() : Expired(nullptr) {};
- explicit ExpiredLattice(LoanSet S) : Expired(S) {}
+ explicit ExpiredLattice(ExpiredLoanMap M) : Expired(M) {}
bool operator==(const ExpiredLattice &Other) const {
return Expired == Other.Expired;
@@ -851,8 +921,8 @@ struct ExpiredLattice {
OS << "ExpiredLattice State:\n";
if (Expired.isEmpty())
OS << " <empty>\n";
- for (const LoanID &LID : Expired)
- OS << " Loan " << LID << " is expired\n";
+ for (const auto &[ID, _] : Expired)
+ OS << " Loan " << ID << " is expired\n";
}
};
@@ -861,26 +931,31 @@ class ExpiredLoansAnalysis
: public DataflowAnalysis<ExpiredLoansAnalysis, ExpiredLattice,
Direction::Forward> {
- LoanSet::Factory &Factory;
+ ExpiredLoanMap::Factory &Factory;
public:
ExpiredLoansAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
LifetimeFactory &Factory)
- : DataflowAnalysis(C, AC, F), Factory(Factory.LoanSetFactory) {}
+ : DataflowAnalysis(C, AC, F), Factory(Factory.ExpiredLoanMapFactory) {}
using Base::transfer;
StringRef getAnalysisName() const { return "ExpiredLoans"; }
- Lattice getInitialState() { return Lattice(Factory.getEmptySet()); }
+ Lattice getInitialState() { return Lattice(Factory.getEmptyMap()); }
- /// Merges two lattices by taking the union of the expired loan sets.
- Lattice join(Lattice L1, Lattice L2) const {
- return Lattice(utils::join(L1.Expired, L2.Expired, Factory));
+ /// Merges two lattices by taking the union of the two expired loans.
+ Lattice join(Lattice L1, Lattice L2) {
+ return Lattice(
+ utils::join(L1.Expired, L2.Expired, Factory,
+ // Take the last expiry fact to make this hermetic.
+ [](const ExpireFact *F1, const ExpireFact *F2) {
+ return F1->getExpiryLoc() > F2->getExpiryLoc() ? F1 : F2;
+ }));
}
Lattice transfer(Lattice In, const ExpireFact &F) {
- return Lattice(Factory.add(In.Expired, F.getLoanID()));
+ return Lattice(Factory.add(In.Expired, F.getLoanID(), &F));
}
// Removes the loan from the set of expired loans.
@@ -912,15 +987,116 @@ public:
Lattice transfer(Lattice In, const IssueFact &F) {
return Lattice(Factory.remove(In.Expired, F.getLoanID()));
}
+
+ ExpiredLoanMap getExpiredLoans(ProgramPoint P) { return getState(P).Expired; }
};
// ========================================================================= //
-// TODO:
-// - Modify loan expiry analysis to answer `bool isExpired(Loan L, Point P)`
-// - Modify origin liveness analysis to answer `bool isLive(Origin O, Point P)`
-// - Using the above three to perform the final error reporting.
+// Lifetime checker and Error reporter
// ========================================================================= //
+/// Struct to store the complete context for a potential lifetime violation.
+struct PendingWarning {
+ SourceLocation ExpiryLoc; // Where the loan expired.
+ const Expr *UseExpr; // Where the origin holding this loan was used.
+ Confidence ConfidenceLevel;
+};
+
+class LifetimeChecker {
+private:
+ llvm::DenseMap<LoanID, PendingWarning> FinalWarningsMap;
+ LoanPropagationAnalysis &LoanPropagation;
+ ExpiredLoansAnalysis &ExpiredLoans;
+ FactManager &FactMgr;
+ AnalysisDeclContext &ADC;
+ LifetimeSafetyReporter *Reporter;
+
+public:
+ LifetimeChecker(LoanPropagationAnalysis &LPA, ExpiredLoansAnalysis &ELA,
+ FactManager &FM, AnalysisDeclContext &ADC,
+ LifetimeSafetyReporter *Reporter)
+ : LoanPropagation(LPA), ExpiredLoans(ELA), FactMgr(FM), ADC(ADC),
+ Reporter(Reporter) {}
+
+ void run() {
+ llvm::TimeTraceScope TimeProfile("LifetimeChecker");
+ for (const CFGBlock *B : *ADC.getAnalysis<PostOrderCFGView>())
+ for (const Fact *F : FactMgr.getFacts(B))
+ if (const auto *UF = F->getAs<UseFact>())
+ checkUse(UF);
+ issuePendingWarnings();
+ }
+
+ /// Checks for use-after-free errors for a given use of an Origin.
+ ///
+ /// This method is called for each 'UseFact' identified in the control flow
+ /// graph. It determines if the loans held by the used origin have expired
+ /// at the point of use.
+ void checkUse(const UseFact *UF) {
+
+ OriginID O = UF->getUsedOrigin();
+
+ // Get the set of loans that the origin might hold at this program point.
+ LoanSet HeldLoans = LoanPropagation.getLoans(O, UF);
+
+ // Get the set of all loans that have expired at this program point.
+ ExpiredLoanMap AllExpiredLoans = ExpiredLoans.getExpiredLoans(UF);
+
+ // If the pointer holds no loans or no loans have expired, there's nothing
+ // to check.
+ if (HeldLoans.isEmpty() || AllExpiredLoans.isEmpty())
+ return;
+
+ // Identify loans that which have expired but are held by the pointer. Using
+ // them is a use-after-free.
+ llvm::SmallVector<LoanID> DefaultedLoans;
+ // A definite UaF error occurs if all loans the origin might hold have
+ // expired.
+ bool IsDefiniteError = true;
+ for (LoanID L : HeldLoans) {
+ if (AllExpiredLoans.contains(L))
+ DefaultedLoans.push_back(L);
+ else
+ // If at least one loan is not expired, this use is not a definite UaF.
+ IsDefiniteError = false;
+ }
+ // If there are no defaulted loans, the use is safe.
+ if (DefaultedLoans.empty())
+ return;
+
+ // Determine the confidence level of the error (definite or maybe).
+ Confidence CurrentConfidence =
+ IsDefiniteError ? Confidence::Definite : Confidence::Maybe;
+
+ // For each expired loan, create a pending warning.
+ for (LoanID DefaultedLoan : DefaultedLoans) {
+ // If we already have a warning for this loan with a higher or equal
+ // confidence, skip this one.
+ if (FinalWarningsMap.count(DefaultedLoan) &&
+ CurrentConfidence <= FinalWarningsMap[DefaultedLoan].ConfidenceLevel)
+ continue;
+
+ auto *EF = AllExpiredLoans.lookup(DefaultedLoan);
+ assert(EF && "Could not find ExpireFact for an expired loan.");
+
+ FinalWarningsMap[DefaultedLoan] = {/*ExpiryLoc=*/(*EF)->getExpiryLoc(),
+ /*UseExpr=*/UF->getUseExpr(),
+ /*ConfidenceLevel=*/CurrentConfidence};
+ }
+ }
+
+ void issuePendingWarnings() {
+ if (!Reporter)
+ return;
+ for (const auto &[LID, Warning] : FinalWarningsMap) {
+ const Loan &L = FactMgr.getLoanMgr().getLoan(LID);
+ const Expr *IssueExpr = L.IssueExpr;
+ Reporter->reportUseAfterFree(IssueExpr, Warning.UseExpr,
+ Warning.ExpiryLoc, Warning.ConfidenceLevel);
+ }
+ }
+};
+
// ========================================================================= //
// LifetimeSafetyAnalysis Class Implementation
// ========================================================================= //
@@ -928,8 +1104,9 @@ public:
// We need this here for unique_ptr with forward declared class.
LifetimeSafetyAnalysis::~LifetimeSafetyAnalysis() = default;
-LifetimeSafetyAnalysis::LifetimeSafetyAnalysis(AnalysisDeclContext &AC)
- : AC(AC), Factory(std::make_unique<LifetimeFactory>()),
+LifetimeSafetyAnalysis::LifetimeSafetyAnalysis(AnalysisDeclContext &AC,
+ LifetimeSafetyReporter *Reporter)
+ : AC(AC), Reporter(Reporter), Factory(std::make_unique<LifetimeFactory>()),
FactMgr(std::make_unique<FactManager>()) {}
void LifetimeSafetyAnalysis::run() {
@@ -952,6 +1129,8 @@ void LifetimeSafetyAnalysis::run() {
/// blocks; only Decls are visible. Therefore, loans in a block that
/// never reach an Origin associated with a Decl can be safely dropped by
/// the analysis.
+ /// 3. Collapse ExpireFacts belonging to same source location into a single
+ /// Fact.
LoanPropagation =
std::make_unique<LoanPropagationAnalysis>(Cfg, AC, *FactMgr, *Factory);
LoanPropagation->run();
@@ -959,6 +1138,10 @@ void LifetimeSafetyAnalysis::run() {
ExpiredLoans =
std::make_unique<ExpiredLoansAnalysis>(Cfg, AC, *FactMgr, *Factory);
ExpiredLoans->run();
+
+ LifetimeChecker Checker(*LoanPropagation, *ExpiredLoans, *FactMgr, AC,
+ Reporter);
+ Checker.run();
}
LoanSet LifetimeSafetyAnalysis::getLoansAtPoint(OriginID OID,
@@ -967,9 +1150,13 @@ LoanSet LifetimeSafetyAnalysis::getLoansAtPoint(OriginID OID,
return LoanPropagation->getLoans(OID, PP);
}
-LoanSet LifetimeSafetyAnalysis::getExpiredLoansAtPoint(ProgramPoint PP) const {
+std::vector<LoanID>
+LifetimeSafetyAnalysis::getExpiredLoansAtPoint(ProgramPoint PP) const {
assert(ExpiredLoans && "ExpiredLoansAnalysis has not been run.");
- return ExpiredLoans->getState(PP).Expired;
+ std::vector<LoanID> Result;
+ for (const auto &pair : ExpiredLoans->getExpiredLoans(PP))
+ Result.push_back(pair.first);
+ return Result;
}
std::optional<OriginID>
@@ -1009,8 +1196,9 @@ llvm::StringMap<ProgramPoint> LifetimeSafetyAnalysis::getTestPoints() const {
}
} // namespace internal
-void runLifetimeSafetyAnalysis(AnalysisDeclContext &AC) {
- internal::LifetimeSafetyAnalysis Analysis(AC);
+void runLifetimeSafetyAnalysis(AnalysisDeclContext &AC,
+ LifetimeSafetyReporter *Reporter) {
+ internal::LifetimeSafetyAnalysis Analysis(AC, Reporter);
Analysis.run();
}
} // namespace clang::lifetimes
diff --git a/clang/lib/Analysis/ThreadSafety.cpp b/clang/lib/Analysis/ThreadSafety.cpp
index c9fd9cc..026d030 100644
--- a/clang/lib/Analysis/ThreadSafety.cpp
+++ b/clang/lib/Analysis/ThreadSafety.cpp
@@ -1929,7 +1929,9 @@ void BuildLockset::handleCall(const Expr *Exp, const NamedDecl *D,
assert(inserted.second && "Are we visiting the same expression again?");
if (isa<CXXConstructExpr>(Exp))
Self = Placeholder;
- if (TagT->getDecl()->hasAttr<ScopedLockableAttr>())
+ if (TagT->getOriginalDecl()
+ ->getMostRecentDecl()
+ ->hasAttr<ScopedLockableAttr>())
Scp = CapabilityExpr(Placeholder, Exp->getType(), /*Neg=*/false);
}
diff --git a/clang/lib/Analysis/ThreadSafetyCommon.cpp b/clang/lib/Analysis/ThreadSafetyCommon.cpp
index ddbd0a9..f560dd8 100644
--- a/clang/lib/Analysis/ThreadSafetyCommon.cpp
+++ b/clang/lib/Analysis/ThreadSafetyCommon.cpp
@@ -84,8 +84,8 @@ static std::pair<StringRef, bool> classifyCapability(QualType QT) {
// which it is. The type should either be a record or a typedef, or a pointer
// or reference thereof.
if (const auto *RT = QT->getAs<RecordType>()) {
- if (const auto *RD = RT->getDecl())
- return classifyCapability(*RD);
+ if (const auto *RD = RT->getOriginalDecl())
+ return classifyCapability(*RD->getDefinitionOrSelf());
} else if (const auto *TT = QT->getAs<TypedefType>()) {
if (const auto *TD = TT->getDecl())
return classifyCapability(*TD);
diff --git a/clang/lib/Analysis/UnsafeBufferUsage.cpp b/clang/lib/Analysis/UnsafeBufferUsage.cpp
index 40dff7e..1d7b872 100644
--- a/clang/lib/Analysis/UnsafeBufferUsage.cpp
+++ b/clang/lib/Analysis/UnsafeBufferUsage.cpp
@@ -182,18 +182,22 @@ public:
return DynamicRecursiveASTVisitor::TraverseUnaryExprOrTypeTraitExpr(Node);
}
- bool TraverseTypeOfExprTypeLoc(TypeOfExprTypeLoc Node) override {
+ bool TraverseTypeOfExprTypeLoc(TypeOfExprTypeLoc Node,
+ bool TraverseQualifier) override {
// Unevaluated context.
if (ignoreUnevaluatedContext)
return true;
- return DynamicRecursiveASTVisitor::TraverseTypeOfExprTypeLoc(Node);
+ return DynamicRecursiveASTVisitor::TraverseTypeOfExprTypeLoc(
+ Node, TraverseQualifier);
}
- bool TraverseDecltypeTypeLoc(DecltypeTypeLoc Node) override {
+ bool TraverseDecltypeTypeLoc(DecltypeTypeLoc Node,
+ bool TraverseQualifier) override {
// Unevaluated context.
if (ignoreUnevaluatedContext)
return true;
- return DynamicRecursiveASTVisitor::TraverseDecltypeTypeLoc(Node);
+ return DynamicRecursiveASTVisitor::TraverseDecltypeTypeLoc(
+ Node, TraverseQualifier);
}
bool TraverseCXXNoexceptExpr(CXXNoexceptExpr *Node) override {
@@ -1986,6 +1990,14 @@ public:
const auto *FD = dyn_cast<FunctionDecl>(CE->getDirectCallee());
if (!FD)
return false;
+
+ bool IsGlobalAndNotInAnyNamespace =
+ FD->isGlobal() && !FD->getEnclosingNamespaceContext()->isNamespace();
+
+ // A libc function must either be in the std:: namespace or a global
+ // function that is not in any namespace:
+ if (!FD->isInStdNamespace() && !IsGlobalAndNotInAnyNamespace)
+ return false;
auto isSingleStringLiteralArg = false;
if (CE->getNumArgs() == 1) {
isSingleStringLiteralArg =
@@ -2244,7 +2256,7 @@ namespace {
// declarations to its uses and make sure we've covered all uses with our
// analysis before we try to fix the declaration.
class DeclUseTracker {
- using UseSetTy = llvm::SmallSet<const DeclRefExpr *, 16>;
+ using UseSetTy = llvm::SmallPtrSet<const DeclRefExpr *, 16>;
using DefMapTy = llvm::DenseMap<const VarDecl *, const DeclStmt *>;
// Allocate on the heap for easier move.
generated by cgit v1.1 at 2025-08-19 22:09:19 +0000