https://github.com/melver updated https://github.com/llvm/llvm-project/pull/142955
>From b4b995bdd7b46ca64440781f214ae6c11de4501b Mon Sep 17 00:00:00 2001 From: Marco Elver <el...@google.com> Date: Wed, 21 May 2025 23:49:48 +0200 Subject: [PATCH] Thread Safety Analysis: Basic capability alias-analysis Add basic alias analysis for capabilities by reusing LocalVariableMap, which tracks currently valid definitions of variables (where possible). Aliases created through complex control flow are not tracked. For example, the analysis will no longer generate false positives for cases such as: void testNestedAccess(Container *c) { Foo *ptr = &c->foo; ptr->mu.Lock(); c->foo.data = 42; // OK - no false positive ptr->mu.Unlock(); } void testNestedAcquire(Container *c) EXCLUSIVE_LOCK_FUNCTION(&c->foo.mu) { Foo *buf = &c->foo; buf->mu.Lock(); // OK - no false positive } This implementation would satisfy the basic needs of addressing the concerns for Linux kernel application [1]. Link: https://lore.kernel.org/all/CANpmjNPquO=W1JAh1FNQb8pMQjgeZAKCPQUAd7qUg=5pjJ6x=q...@mail.gmail.com/ [1] --- .../Analysis/Analyses/ThreadSafetyCommon.h | 18 +- clang/lib/Analysis/ThreadSafety.cpp | 83 +++++++-- clang/lib/Analysis/ThreadSafetyCommon.cpp | 33 +++- clang/test/Sema/warn-thread-safety-analysis.c | 6 +- .../SemaCXX/warn-thread-safety-analysis.cpp | 174 +++++++++++++++++- 5 files changed, 291 insertions(+), 23 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h index 6c97905a2d7f9..e152b17bde868 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h +++ b/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h @@ -35,6 +35,7 @@ #include "llvm/ADT/PointerUnion.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Casting.h" +#include <functional> #include <sstream> #include <string> #include <utility> @@ -386,6 +387,11 @@ class SExprBuilder { SelfVar->setKind(til::Variable::VK_SFun); } + // Create placeholder for this: we don't know the VarDecl on construction yet. + til::LiteralPtr *createThisPlaceholder() { + return new (Arena) til::LiteralPtr(nullptr); + } + // Translate a clang expression in an attribute to a til::SExpr. // Constructs the context from D, DeclExp, and SelfDecl. CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D, @@ -394,8 +400,8 @@ class SExprBuilder { CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx); - // Translate a variable reference. - til::LiteralPtr *createVariable(const VarDecl *VD); + // Translate a VarDecl to its canonical TIL expression. + til::SExpr *translateVariable(const VarDecl *VD, CallingContext *Ctx); // Translate a clang statement or expression to a TIL expression. // Also performs substitution of variables; Ctx provides the context. @@ -412,6 +418,10 @@ class SExprBuilder { const til::SCFG *getCFG() const { return Scfg; } til::SCFG *getCFG() { return Scfg; } + void setLookupLocalVarExpr(std::function<const Expr *(const NamedDecl *)> F) { + LookupLocalVarExpr = std::move(F); + } + private: // We implement the CFGVisitor API friend class CFGWalker; @@ -445,6 +455,7 @@ class SExprBuilder { const AbstractConditionalOperator *C, CallingContext *Ctx); til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); + til::SExpr *translateStmtExpr(const StmtExpr *SE, CallingContext *Ctx); // Map from statements in the clang CFG to SExprs in the til::SCFG. using StatementMap = llvm::DenseMap<const Stmt *, til::SExpr *>; @@ -531,6 +542,9 @@ class SExprBuilder { std::vector<til::Phi *> IncompleteArgs; til::BasicBlock *CurrentBB = nullptr; BlockInfo *CurrentBlockInfo = nullptr; + + // Context-dependent lookup of currently valid definitions of local variables. + std::function<const Expr *(const NamedDecl *)> LookupLocalVarExpr; }; #ifndef NDEBUG diff --git a/clang/lib/Analysis/ThreadSafety.cpp b/clang/lib/Analysis/ThreadSafety.cpp index 80e7c8eff671a..b5d46b572a9a8 100644 --- a/clang/lib/Analysis/ThreadSafety.cpp +++ b/clang/lib/Analysis/ThreadSafety.cpp @@ -609,6 +609,7 @@ class VarMapBuilder : public ConstStmtVisitor<VarMapBuilder> { void VisitDeclStmt(const DeclStmt *S); void VisitBinaryOperator(const BinaryOperator *BO); + void VisitCallExpr(const CallExpr *CE); }; } // namespace @@ -654,6 +655,43 @@ void VarMapBuilder::VisitBinaryOperator(const BinaryOperator *BO) { } } +// Invalidates local variable definitions if variable escaped. +void VarMapBuilder::VisitCallExpr(const CallExpr *CE) { + const FunctionDecl *FD = CE->getDirectCallee(); + if (!FD) + return; + + for (unsigned Idx = 0; Idx < CE->getNumArgs(); ++Idx) { + if (Idx >= FD->getNumParams()) + break; + + const Expr *Arg = CE->getArg(Idx)->IgnoreParenImpCasts(); + const ParmVarDecl *PVD = FD->getParamDecl(Idx); + QualType ParamType = PVD->getType(); + + // Potential reassignment if passed by non-const reference / pointer. + const ValueDecl *VDec = nullptr; + if (ParamType->isReferenceType() && + !ParamType->getPointeeType().isConstQualified()) { + if (const auto *DRE = dyn_cast<DeclRefExpr>(Arg)) + VDec = DRE->getDecl(); + } else if (ParamType->isPointerType() && + !ParamType->getPointeeType().isConstQualified()) { + if (const auto *UO = dyn_cast<UnaryOperator>(Arg); + UO && UO->getOpcode() == UO_AddrOf) { + const Expr *SE = UO->getSubExpr()->IgnoreParenImpCasts(); + if (const auto *DRE = dyn_cast<DeclRefExpr>(SE)) + VDec = DRE->getDecl(); + } + } + + if (VDec && Ctx.lookup(VDec)) { + Ctx = VMap->clearDefinition(VDec, Ctx); + VMap->saveContext(CE, Ctx); + } + } +} + // Computes the intersection of two contexts. The intersection is the // set of variables which have the same definition in both contexts; // variables with different definitions are discarded. @@ -1141,11 +1179,10 @@ class ThreadSafetyAnalyzer { void warnIfMutexNotHeld(const FactSet &FSet, const NamedDecl *D, const Expr *Exp, AccessKind AK, Expr *MutexExp, - ProtectedOperationKind POK, til::LiteralPtr *Self, + ProtectedOperationKind POK, til::SExpr *Self, SourceLocation Loc); void warnIfMutexHeld(const FactSet &FSet, const NamedDecl *D, const Expr *Exp, - Expr *MutexExp, til::LiteralPtr *Self, - SourceLocation Loc); + Expr *MutexExp, til::SExpr *Self, SourceLocation Loc); void checkAccess(const FactSet &FSet, const Expr *Exp, AccessKind AK, ProtectedOperationKind POK); @@ -1599,7 +1636,7 @@ class BuildLockset : public ConstStmtVisitor<BuildLockset> { } void handleCall(const Expr *Exp, const NamedDecl *D, - til::LiteralPtr *Self = nullptr, + til::SExpr *Self = nullptr, SourceLocation Loc = SourceLocation()); void examineArguments(const FunctionDecl *FD, CallExpr::const_arg_iterator ArgBegin, @@ -1611,7 +1648,14 @@ class BuildLockset : public ConstStmtVisitor<BuildLockset> { const FactSet &FunctionExitFSet) : ConstStmtVisitor<BuildLockset>(), Analyzer(Anlzr), FSet(Info.EntrySet), FunctionExitFSet(FunctionExitFSet), LVarCtx(Info.EntryContext), - CtxIndex(Info.EntryIndex) {} + CtxIndex(Info.EntryIndex) { + Analyzer->SxBuilder.setLookupLocalVarExpr([this](const NamedDecl *D) { + auto Ctx = LVarCtx; + return Analyzer->LocalVarMap.lookupExpr(D, Ctx); + }); + } + + ~BuildLockset() { Analyzer->SxBuilder.setLookupLocalVarExpr(nullptr); } void VisitUnaryOperator(const UnaryOperator *UO); void VisitBinaryOperator(const BinaryOperator *BO); @@ -1629,7 +1673,7 @@ class BuildLockset : public ConstStmtVisitor<BuildLockset> { /// of at least the passed in AccessKind. void ThreadSafetyAnalyzer::warnIfMutexNotHeld( const FactSet &FSet, const NamedDecl *D, const Expr *Exp, AccessKind AK, - Expr *MutexExp, ProtectedOperationKind POK, til::LiteralPtr *Self, + Expr *MutexExp, ProtectedOperationKind POK, til::SExpr *Self, SourceLocation Loc) { LockKind LK = getLockKindFromAccessKind(AK); CapabilityExpr Cp = SxBuilder.translateAttrExpr(MutexExp, D, Exp, Self); @@ -1688,8 +1732,7 @@ void ThreadSafetyAnalyzer::warnIfMutexNotHeld( /// Warn if the LSet contains the given lock. void ThreadSafetyAnalyzer::warnIfMutexHeld(const FactSet &FSet, const NamedDecl *D, const Expr *Exp, - Expr *MutexExp, - til::LiteralPtr *Self, + Expr *MutexExp, til::SExpr *Self, SourceLocation Loc) { CapabilityExpr Cp = SxBuilder.translateAttrExpr(MutexExp, D, Exp, Self); if (Cp.isInvalid()) { @@ -1857,7 +1900,7 @@ void ThreadSafetyAnalyzer::checkPtAccess(const FactSet &FSet, const Expr *Exp, /// of an implicitly called cleanup function. /// \param Loc If \p Exp = nullptr, the location. void BuildLockset::handleCall(const Expr *Exp, const NamedDecl *D, - til::LiteralPtr *Self, SourceLocation Loc) { + til::SExpr *Self, SourceLocation Loc) { CapExprSet ExclusiveLocksToAdd, SharedLocksToAdd; CapExprSet ExclusiveLocksToRemove, SharedLocksToRemove, GenericLocksToRemove; CapExprSet ScopedReqsAndExcludes; @@ -1869,7 +1912,7 @@ void BuildLockset::handleCall(const Expr *Exp, const NamedDecl *D, const auto *TagT = Exp->getType()->getAs<TagType>(); if (D->hasAttrs() && TagT && Exp->isPRValue()) { til::LiteralPtr *Placeholder = - Analyzer->SxBuilder.createVariable(nullptr); + Analyzer->SxBuilder.createThisPlaceholder(); [[maybe_unused]] auto inserted = Analyzer->ConstructedObjects.insert({Exp, Placeholder}); assert(inserted.second && "Are we visiting the same expression again?"); @@ -2158,6 +2201,9 @@ void BuildLockset::examineArguments(const FunctionDecl *FD, } void BuildLockset::VisitCallExpr(const CallExpr *Exp) { + // adjust the context + LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, Exp, LVarCtx); + if (const auto *CE = dyn_cast<CXXMemberCallExpr>(Exp)) { const auto *ME = dyn_cast<MemberExpr>(CE->getCallee()); // ME can be null when calling a method pointer @@ -2545,7 +2591,8 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { } if (UnderlyingLocks.empty()) continue; - CapabilityExpr Cp(SxBuilder.createVariable(Param), StringRef(), + CapabilityExpr Cp(SxBuilder.translateVariable(Param, nullptr), + StringRef(), /*Neg=*/false, /*Reentrant=*/false); auto ScopedEntry = std::make_unique<ScopedLockableFactEntry>( Cp, Param->getLocation(), FactEntry::Declared); @@ -2662,17 +2709,19 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { if (!DD->hasAttrs()) break; - LocksetBuilder.handleCall(nullptr, DD, - SxBuilder.createVariable(AD.getVarDecl()), - AD.getTriggerStmt()->getEndLoc()); + LocksetBuilder.handleCall( + nullptr, DD, + SxBuilder.translateVariable(AD.getVarDecl(), nullptr), + AD.getTriggerStmt()->getEndLoc()); break; } case CFGElement::CleanupFunction: { const CFGCleanupFunction &CF = BI.castAs<CFGCleanupFunction>(); - LocksetBuilder.handleCall(/*Exp=*/nullptr, CF.getFunctionDecl(), - SxBuilder.createVariable(CF.getVarDecl()), - CF.getVarDecl()->getLocation()); + LocksetBuilder.handleCall( + /*Exp=*/nullptr, CF.getFunctionDecl(), + SxBuilder.translateVariable(CF.getVarDecl(), nullptr), + CF.getVarDecl()->getLocation()); break; } diff --git a/clang/lib/Analysis/ThreadSafetyCommon.cpp b/clang/lib/Analysis/ThreadSafetyCommon.cpp index ddbd0a9ca904b..bf32f1f246c28 100644 --- a/clang/lib/Analysis/ThreadSafetyCommon.cpp +++ b/clang/lib/Analysis/ThreadSafetyCommon.cpp @@ -241,7 +241,24 @@ CapabilityExpr SExprBuilder::translateAttrExpr(const Expr *AttrExp, return CapabilityExpr(E, AttrExp->getType(), Neg); } -til::LiteralPtr *SExprBuilder::createVariable(const VarDecl *VD) { +til::SExpr *SExprBuilder::translateVariable(const VarDecl *VD, + CallingContext *Ctx) { + assert(VD); + + QualType Ty = VD->getType(); + if (Ty->isPointerType()) { + if (LookupLocalVarExpr) { + // Substitute local variable aliases with a canonical definition. + if (const Expr *E = LookupLocalVarExpr(VD)) { + // Guard against recursion on self-assignment (e.g. `T *x = x;`). + if (const auto *DRE = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) + if (DRE->getDecl()->getCanonicalDecl() == VD->getCanonicalDecl()) + return new (Arena) til::LiteralPtr(VD); + return translate(E, Ctx); + } + } + } + return new (Arena) til::LiteralPtr(VD); } @@ -313,6 +330,8 @@ til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) { case Stmt::DeclStmtClass: return translateDeclStmt(cast<DeclStmt>(S), Ctx); + case Stmt::StmtExprClass: + return translateStmtExpr(cast<StmtExpr>(S), Ctx); default: break; } @@ -353,6 +372,9 @@ til::SExpr *SExprBuilder::translateDeclRefExpr(const DeclRefExpr *DRE, : cast<ObjCMethodDecl>(D)->getCanonicalDecl()->getParamDecl(I); } + if (const auto *VarD = dyn_cast<VarDecl>(VD)) + return translateVariable(VarD, Ctx); + // For non-local variables, treat it as a reference to a named object. return new (Arena) til::LiteralPtr(VD); } @@ -691,6 +713,15 @@ SExprBuilder::translateDeclStmt(const DeclStmt *S, CallingContext *Ctx) { return nullptr; } +til::SExpr *SExprBuilder::translateStmtExpr(const StmtExpr *SE, + CallingContext *Ctx) { + // The value of a statement expression is the value of the last statement, + // which must be an expression. + const CompoundStmt *CS = SE->getSubStmt(); + return CS->body_empty() ? new (Arena) til::Undefined(SE) + : translate(CS->body_back(), Ctx); +} + // If (E) is non-trivial, then add it to the current basic block, and // update the statement map so that S refers to E. Returns a new variable // that refers to E. diff --git a/clang/test/Sema/warn-thread-safety-analysis.c b/clang/test/Sema/warn-thread-safety-analysis.c index b43f97af9162e..549cb1231baa6 100644 --- a/clang/test/Sema/warn-thread-safety-analysis.c +++ b/clang/test/Sema/warn-thread-safety-analysis.c @@ -184,9 +184,13 @@ int main(void) { /// Cleanup functions { struct Mutex* const __attribute__((cleanup(unlock_scope))) scope = &mu1; - mutex_exclusive_lock(scope); // Note that we have to lock through scope, because no alias analysis! + mutex_exclusive_lock(scope); // Lock through scope works. // Cleanup happens automatically -> no warning. } + { + struct Mutex* const __attribute__((unused, cleanup(unlock_scope))) scope = &mu1; + mutex_exclusive_lock(&mu1); // With basic alias analysis lock through mu1 also works. + } foo_.a_value = 0; // expected-warning {{writing variable 'a_value' requires holding mutex 'mu_' exclusively}} *foo_.a_ptr = 1; // expected-warning {{writing the value pointed to by 'a_ptr' requires holding mutex 'bar.other_mu' exclusively}} diff --git a/clang/test/SemaCXX/warn-thread-safety-analysis.cpp b/clang/test/SemaCXX/warn-thread-safety-analysis.cpp index d82e2484ace1e..9f97c3bf9b161 100644 --- a/clang/test/SemaCXX/warn-thread-safety-analysis.cpp +++ b/clang/test/SemaCXX/warn-thread-safety-analysis.cpp @@ -1556,9 +1556,9 @@ void main() { Child *c; Base *b = c; - b->func1(); // expected-warning {{calling function 'func1' requires holding mutex 'b->mu_' exclusively}} + b->func1(); // expected-warning {{calling function 'func1' requires holding mutex 'c->mu_' exclusively}} b->mu_.Lock(); - b->func2(); // expected-warning {{cannot call function 'func2' while mutex 'b->mu_' is held}} + b->func2(); // expected-warning {{cannot call function 'func2' while mutex 'c->mu_' is held}} b->mu_.Unlock(); c->func1(); // expected-warning {{calling function 'func1' requires holding mutex 'c->mu_' exclusively}} @@ -7238,3 +7238,173 @@ class TestNegativeWithReentrantMutex { }; } // namespace Reentrancy + +// Tests for tracking aliases of capabilities. +namespace CapabilityAliases { +struct Foo { + Mutex mu; + int data GUARDED_BY(mu); +}; + +void escapeAlias(int a, Foo *&ptr); +void escapeAlias(int b, Foo **ptr); +void passByConstRef(Foo* const& ptr); + +void testBasicPointerAlias(Foo *f) { + Foo *ptr = f; + ptr->mu.Lock(); // lock through alias + f->data = 42; // access through original + ptr->mu.Unlock(); // unlock through alias +} + +void testBasicPointerAliasNoInit(Foo *f) { + Foo *ptr; + + ptr = nullptr; + ptr = f; + ptr->mu.Lock(); + f->data = 42; + ptr->mu.Unlock(); + ptr = nullptr; +} + +void testPointerAliasNoEscape1(Foo *f) { + Foo *ptr = f; + testBasicPointerAlias(ptr); // pass alias by value + + ptr->mu.Lock(); + f->data = 42; + ptr->mu.Unlock(); +} + +void testPointerAliasNoEscape2(Foo *f) { + Foo *ptr = f; + passByConstRef(ptr); // pass alias by const ref + + ptr->mu.Lock(); + f->data = 42; + ptr->mu.Unlock(); +} + +void testPointerAliasEscape1(Foo *f) { + Foo *ptr = f; + escapeAlias(0, ptr); + + ptr->mu.Lock(); + f->data = 42; // expected-warning{{writing variable 'data' requires holding mutex 'f->mu' exclusively}} \ + // expected-note{{found near match 'ptr->mu'}} + ptr->mu.Unlock(); +} + +void testPointerAliasEscape2(Foo *f) { + Foo *ptr = f; + escapeAlias(0, &ptr); + + ptr->mu.Lock(); + f->data = 42; // expected-warning{{writing variable 'data' requires holding mutex 'f->mu' exclusively}} \ + // expected-note{{found near match 'ptr->mu'}} + ptr->mu.Unlock(); +} + +void testPointerAliasEscapeAndReset(Foo *f) { + Foo *ptr; + + ptr = f; + escapeAlias(0, &ptr); + ptr = f; + + ptr->mu.Lock(); + f->data = 42; + ptr->mu.Unlock(); +} + +void testReassignment() { + Foo f1, f2; + Foo *ptr = &f1; + ptr->mu.Lock(); + f1.data = 42; + ptr->mu.Unlock(); + + ptr = &f2; + ptr->mu.Lock(); + f2.data = 42; + f1.data = 42; // expected-warning{{writing variable 'data' requires holding mutex 'f1.mu'}} \ + // expected-note{{found near match 'f2.mu'}} + ptr->mu.Unlock(); +} + +// Nested field access through pointer +struct Container { + Foo foo; +}; + +void testNestedAccess(Container *c) { + Foo *ptr = &c->foo; // pointer to nested field + ptr->mu.Lock(); + c->foo.data = 42; + ptr->mu.Unlock(); +} + +void testNestedAcquire(Container *c) EXCLUSIVE_LOCK_FUNCTION(&c->foo.mu) { + Foo *buf = &c->foo; + buf->mu.Lock(); +} + +struct ContainerOfPtr { + Foo *foo_ptr; +}; + +void testIndirectAccess(ContainerOfPtr *fc) { + Foo *ptr = fc->foo_ptr; // get pointer + ptr->mu.Lock(); + fc->foo_ptr->data = 42; // access via original + ptr->mu.Unlock(); +} + +// FIXME: No alias tracking through complex control flow. +void testComplexControlFlow(Foo *f1, Foo *f2, bool cond) { + Foo *ptr; + if (cond) { + ptr = f1; + } else { + ptr = f2; + } + ptr->mu.Lock(); + if (cond) { + f1->data = 42; // expected-warning{{writing variable 'data' requires holding mutex 'f1->mu' exclusively}} \ + // expected-note{{found near match 'ptr->mu'}} + } else { + f2->data = 42; // expected-warning{{writing variable 'data' requires holding mutex 'f2->mu' exclusively}} \ + // expected-note{{found near match 'ptr->mu'}} + } + ptr->mu.Unlock(); +} + +void testLockFunction(Foo *f) EXCLUSIVE_LOCK_FUNCTION(&f->mu) { + Mutex *mu = &f->mu; + mu->Lock(); +} + +void testUnlockFunction(Foo *f) UNLOCK_FUNCTION(&f->mu) { + Mutex *mu = &f->mu; + mu->Unlock(); +} + +// Semantically UB, but let's not crash the compiler with this (should be +// handled by -Wuninitialized). +void testSelfInit() { + Mutex *mu = mu; // don't do this at home + mu->Lock(); + mu->Unlock(); +} + +// This is an idiom to deal with "pointer to returned object has a lock held, +// but you must unlock it later" where the statement expression would be hidden +// behind a macro. +Foo *returnsFoo(); +void lockWithinStatementExpr() { + Foo *f = ({ auto x = returnsFoo(); x->mu.Lock(); x; }); + f->data = 42; + f->mu.Unlock(); +} +} // namespace CapabilityAliases _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits