Skip to content

Commit 4980df6

Browse files
delesleydelesley
committedFeb 3, 2015
Thread Safety Analysis: add support for before/after annotations on mutexes.
These checks detect potential deadlocks caused by inconsistent lock ordering. The checks are implemented under the -Wthread-safety-beta flag. llvm-svn: 227997
1 parent 57775cd commit 4980df6

File tree

8 files changed

+480
-22
lines changed

8 files changed

+480
-22
lines changed
 

‎clang/include/clang/Analysis/Analyses/ThreadSafety.h

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,8 @@
2626
namespace clang {
2727
namespace threadSafety {
2828

29+
class BeforeSet;
30+
2931
/// This enum distinguishes between different kinds of operations that may
3032
/// need to be protected by locks. We use this enum in error handling.
3133
enum ProtectedOperationKind {
@@ -183,6 +185,14 @@ class ThreadSafetyHandler {
183185
virtual void handleFunExcludesLock(StringRef Kind, Name FunName,
184186
Name LockName, SourceLocation Loc) {}
185187

188+
189+
/// Warn that L1 cannot be acquired before L2.
190+
virtual void handleLockAcquiredBefore(StringRef Kind, Name L1Name,
191+
Name L2Name, SourceLocation Loc) {}
192+
193+
/// Warn that there is a cycle in acquired_before/after dependencies.
194+
virtual void handleBeforeAfterCycle(Name L1Name, SourceLocation Loc) {}
195+
186196
/// Called by the analysis when starting analysis of a function.
187197
/// Used to issue suggestions for changes to annotations.
188198
virtual void enterFunction(const FunctionDecl *FD) {}
@@ -203,7 +213,8 @@ class ThreadSafetyHandler {
203213
/// at the end of each block, and issue warnings for thread safety violations.
204214
/// Each block in the CFG is traversed exactly once.
205215
void runThreadSafetyAnalysis(AnalysisDeclContext &AC,
206-
ThreadSafetyHandler &Handler);
216+
ThreadSafetyHandler &Handler,
217+
BeforeSet **Bset);
207218

208219
/// \brief Helper function that returns a LockKind required for the given level
209220
/// of access.

‎clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -286,6 +286,14 @@ class CapabilityExpr {
286286
sx::partiallyMatches(CapExpr, other.CapExpr);
287287
}
288288

289+
const ValueDecl* valueDecl() const {
290+
if (Negated)
291+
return nullptr;
292+
if (auto *P = dyn_cast<til::Project>(CapExpr))
293+
return P->clangDecl();
294+
return nullptr;
295+
}
296+
289297
std::string toString() const {
290298
if (Negated)
291299
return "!" + sx::toString(CapExpr);

‎clang/include/clang/Basic/DiagnosticSemaKinds.td

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2394,6 +2394,13 @@ def warn_fun_excludes_mutex : Warning<
23942394
def warn_cannot_resolve_lock : Warning<
23952395
"cannot resolve lock expression">,
23962396
InGroup<ThreadSafetyAnalysis>, DefaultIgnore;
2397+
def warn_acquired_before : Warning<
2398+
"%0 '%1' must be acquired before '%2'">,
2399+
InGroup<ThreadSafetyAnalysis>, DefaultIgnore;
2400+
def warn_acquired_before_after_cycle : Warning<
2401+
"Cycle in acquired_before/after dependencies, starting with '%0'">,
2402+
InGroup<ThreadSafetyAnalysis>, DefaultIgnore;
2403+
23972404

23982405
// Thread safety warnings negative capabilities
23992406
def warn_acquire_requires_negative_cap : Warning<

‎clang/include/clang/Sema/Sema.h

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -199,6 +199,11 @@ namespace sema {
199199
class TemplateDeductionInfo;
200200
}
201201

202+
namespace threadSafety {
203+
class BeforeSet;
204+
void threadSafetyCleanup(BeforeSet* Cache);
205+
}
206+
202207
// FIXME: No way to easily map from TemplateTypeParmTypes to
203208
// TemplateTypeParmDecls, so we have this horrible PointerUnion.
204209
typedef std::pair<llvm::PointerUnion<const TemplateTypeParmType*, NamedDecl*>,
@@ -6708,6 +6713,7 @@ class Sema {
67086713

67096714
/// \brief Worker object for performing CFG-based warnings.
67106715
sema::AnalysisBasedWarnings AnalysisWarnings;
6716+
threadSafety::BeforeSet *ThreadSafetyDeclCache;
67116717

67126718
/// \brief An entity for which implicit template instantiation is required.
67136719
///

‎clang/lib/Analysis/ThreadSafety.cpp

Lines changed: 214 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -101,17 +101,22 @@ class FactEntry : public CapabilityExpr {
101101
LockKind LKind; ///< exclusive or shared
102102
SourceLocation AcquireLoc; ///< where it was acquired.
103103
bool Asserted; ///< true if the lock was asserted
104+
bool Declared; ///< true if the lock was declared
104105

105106
public:
106107
FactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc,
107-
bool Asrt)
108-
: CapabilityExpr(CE), LKind(LK), AcquireLoc(Loc), Asserted(Asrt) {}
108+
bool Asrt, bool Declrd = false)
109+
: CapabilityExpr(CE), LKind(LK), AcquireLoc(Loc), Asserted(Asrt),
110+
Declared(Declrd) {}
109111

110112
virtual ~FactEntry() {}
111113

112-
LockKind kind() const { return LKind; }
114+
LockKind kind() const { return LKind; }
113115
SourceLocation loc() const { return AcquireLoc; }
114116
bool asserted() const { return Asserted; }
117+
bool declared() const { return Declared; }
118+
119+
void setDeclared(bool D) { Declared = D; }
115120

116121
virtual void
117122
handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan,
@@ -231,14 +236,56 @@ class FactSet {
231236

232237
FactEntry *findPartialMatch(FactManager &FM,
233238
const CapabilityExpr &CapE) const {
234-
auto I = std::find_if(begin(), end(), [&](FactID ID) {
239+
auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool {
235240
return FM[ID].partiallyMatches(CapE);
236241
});
237242
return I != end() ? &FM[*I] : nullptr;
238243
}
244+
245+
bool containsMutexDecl(FactManager &FM, const ValueDecl* Vd) const {
246+
auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool {
247+
return FM[ID].valueDecl() == Vd;
248+
});
249+
return I != end();
250+
}
251+
};
252+
253+
254+
class ThreadSafetyAnalyzer;
255+
256+
257+
class BeforeSet {
258+
private:
259+
typedef SmallVector<const ValueDecl*, 4> BeforeVect;
260+
261+
struct BeforeInfo {
262+
BeforeInfo() : Vect(nullptr), Visited(false) { }
263+
264+
std::unique_ptr<BeforeVect> Vect;
265+
int Visited;
266+
};
267+
268+
typedef llvm::DenseMap<const ValueDecl*, BeforeInfo> BeforeMap;
269+
typedef llvm::DenseMap<const ValueDecl*, bool> CycleMap;
270+
271+
public:
272+
BeforeSet() { }
273+
274+
BeforeInfo* insertAttrExprs(const ValueDecl* Vd,
275+
ThreadSafetyAnalyzer& Analyzer);
276+
277+
void checkBeforeAfter(const ValueDecl* Vd,
278+
const FactSet& FSet,
279+
ThreadSafetyAnalyzer& Analyzer,
280+
SourceLocation Loc, StringRef CapKind);
281+
282+
private:
283+
BeforeMap BMap;
284+
CycleMap CycMap;
239285
};
240286

241287

288+
242289
typedef llvm::ImmutableMap<const NamedDecl*, unsigned> LocalVarContext;
243290
class LocalVariableMap;
244291

@@ -853,6 +900,7 @@ class ScopedLockableFactEntry : public FactEntry {
853900
/// \brief Class which implements the core thread safety analysis routines.
854901
class ThreadSafetyAnalyzer {
855902
friend class BuildLockset;
903+
friend class BeforeSet;
856904

857905
llvm::BumpPtrAllocator Bpa;
858906
threadSafety::til::MemRegionRef Arena;
@@ -864,9 +912,11 @@ class ThreadSafetyAnalyzer {
864912
FactManager FactMan;
865913
std::vector<CFGBlockInfo> BlockInfo;
866914

915+
BeforeSet* GlobalBeforeSet;
916+
867917
public:
868-
ThreadSafetyAnalyzer(ThreadSafetyHandler &H)
869-
: Arena(&Bpa), SxBuilder(Arena), Handler(H) {}
918+
ThreadSafetyAnalyzer(ThreadSafetyHandler &H, BeforeSet* Bset)
919+
: Arena(&Bpa), SxBuilder(Arena), Handler(H), GlobalBeforeSet(Bset) {}
870920

871921
bool inCurrentScope(const CapabilityExpr &CapE);
872922

@@ -907,6 +957,136 @@ class ThreadSafetyAnalyzer {
907957
void runAnalysis(AnalysisDeclContext &AC);
908958
};
909959

960+
961+
962+
/// Process acquired_before and acquired_after attributes on Vd.
963+
BeforeSet::BeforeInfo* BeforeSet::insertAttrExprs(const ValueDecl* Vd,
964+
ThreadSafetyAnalyzer& Analyzer) {
965+
// Create a new entry for Vd.
966+
auto& Entry = BMap.FindAndConstruct(Vd);
967+
BeforeInfo* Info = &Entry.second;
968+
BeforeVect* Bv = nullptr;
969+
970+
const AttrVec &ArgAttrs = Vd->getAttrs();
971+
for (Attr* At : ArgAttrs) {
972+
switch (At->getKind()) {
973+
case attr::AcquiredBefore: {
974+
auto *A = cast<AcquiredBeforeAttr>(At);
975+
976+
// Create a new BeforeVect for Vd if necessary.
977+
if (!Bv) {
978+
Bv = new BeforeVect;
979+
Info->Vect.reset(Bv);
980+
}
981+
// Read exprs from the attribute, and add them to BeforeVect.
982+
for (const auto *Arg : A->args()) {
983+
CapabilityExpr Cp =
984+
Analyzer.SxBuilder.translateAttrExpr(Arg, nullptr);
985+
if (const ValueDecl *Cpvd = Cp.valueDecl()) {
986+
Bv->push_back(Cpvd);
987+
auto It = BMap.find(Cpvd);
988+
if (It == BMap.end())
989+
insertAttrExprs(Cpvd, Analyzer);
990+
}
991+
}
992+
break;
993+
}
994+
case attr::AcquiredAfter: {
995+
auto *A = cast<AcquiredAfterAttr>(At);
996+
997+
// Read exprs from the attribute, and add them to BeforeVect.
998+
for (const auto *Arg : A->args()) {
999+
CapabilityExpr Cp =
1000+
Analyzer.SxBuilder.translateAttrExpr(Arg, nullptr);
1001+
if (const ValueDecl *ArgVd = Cp.valueDecl()) {
1002+
// Get entry for mutex listed in attribute
1003+
BeforeInfo* ArgInfo;
1004+
auto It = BMap.find(ArgVd);
1005+
if (It == BMap.end())
1006+
ArgInfo = insertAttrExprs(ArgVd, Analyzer);
1007+
else
1008+
ArgInfo = &It->second;
1009+
1010+
// Create a new BeforeVect if necessary.
1011+
BeforeVect* ArgBv = ArgInfo->Vect.get();
1012+
if (!ArgBv) {
1013+
ArgBv = new BeforeVect;
1014+
ArgInfo->Vect.reset(ArgBv);
1015+
}
1016+
ArgBv->push_back(Vd);
1017+
}
1018+
}
1019+
break;
1020+
}
1021+
default:
1022+
break;
1023+
}
1024+
}
1025+
1026+
return Info;
1027+
}
1028+
1029+
1030+
/// Return true if any mutexes in FSet are in the acquired_before set of Vd.
1031+
void BeforeSet::checkBeforeAfter(const ValueDecl* StartVd,
1032+
const FactSet& FSet,
1033+
ThreadSafetyAnalyzer& Analyzer,
1034+
SourceLocation Loc, StringRef CapKind) {
1035+
SmallVector<BeforeInfo*, 8> InfoVect;
1036+
1037+
// Do a depth-first traversal of Vd.
1038+
// Return true if there are cycles.
1039+
std::function<bool (const ValueDecl*)> traverse = [&](const ValueDecl* Vd) {
1040+
if (!Vd)
1041+
return false;
1042+
1043+
BeforeSet::BeforeInfo* Info;
1044+
auto It = BMap.find(Vd);
1045+
if (It == BMap.end())
1046+
Info = insertAttrExprs(Vd, Analyzer);
1047+
else
1048+
Info = &It->second;
1049+
1050+
if (Info->Visited == 1)
1051+
return true;
1052+
1053+
if (Info->Visited == 2)
1054+
return false;
1055+
1056+
BeforeVect* Bv = Info->Vect.get();
1057+
if (!Bv)
1058+
return false;
1059+
1060+
InfoVect.push_back(Info);
1061+
Info->Visited = 1;
1062+
for (auto *Vdb : *Bv) {
1063+
// Exclude mutexes in our immediate before set.
1064+
if (FSet.containsMutexDecl(Analyzer.FactMan, Vdb)) {
1065+
StringRef L1 = StartVd->getName();
1066+
StringRef L2 = Vdb->getName();
1067+
Analyzer.Handler.handleLockAcquiredBefore(CapKind, L1, L2, Loc);
1068+
}
1069+
// Transitively search other before sets, and warn on cycles.
1070+
if (traverse(Vdb)) {
1071+
if (CycMap.find(Vd) == CycMap.end()) {
1072+
CycMap.insert(std::make_pair(Vd, true));
1073+
StringRef L1 = Vd->getName();
1074+
Analyzer.Handler.handleBeforeAfterCycle(L1, Vd->getLocation());
1075+
}
1076+
}
1077+
}
1078+
Info->Visited = 2;
1079+
return false;
1080+
};
1081+
1082+
traverse(StartVd);
1083+
1084+
for (auto* Info : InfoVect)
1085+
Info->Visited = 0;
1086+
}
1087+
1088+
1089+
9101090
/// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs.
9111091
static const ValueDecl *getValueDecl(const Expr *Exp) {
9121092
if (const auto *CE = dyn_cast<ImplicitCastExpr>(Exp))
@@ -1020,7 +1200,13 @@ void ThreadSafetyAnalyzer::addLock(FactSet &FSet,
10201200
}
10211201
}
10221202

1023-
// FIXME: deal with acquired before/after annotations.
1203+
// Check before/after constraints
1204+
if (Handler.issueBetaWarnings() &&
1205+
!Entry->asserted() && !Entry->declared()) {
1206+
GlobalBeforeSet->checkBeforeAfter(Entry->valueDecl(), FSet, *this,
1207+
Entry->loc(), DiagKind);
1208+
}
1209+
10241210
// FIXME: Don't always warn when we have support for reentrant locks.
10251211
if (FSet.findLock(FactMan, *Entry)) {
10261212
if (!Entry->asserted())
@@ -1979,14 +2165,16 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) {
19792165
}
19802166

19812167
// FIXME -- Loc can be wrong here.
1982-
for (const auto &Mu : ExclusiveLocksToAdd)
1983-
addLock(InitialLockset,
1984-
llvm::make_unique<LockableFactEntry>(Mu, LK_Exclusive, Loc),
1985-
CapDiagKind, true);
1986-
for (const auto &Mu : SharedLocksToAdd)
1987-
addLock(InitialLockset,
1988-
llvm::make_unique<LockableFactEntry>(Mu, LK_Shared, Loc),
1989-
CapDiagKind, true);
2168+
for (const auto &Mu : ExclusiveLocksToAdd) {
2169+
auto Entry = llvm::make_unique<LockableFactEntry>(Mu, LK_Exclusive, Loc);
2170+
Entry->setDeclared(true);
2171+
addLock(InitialLockset, std::move(Entry), CapDiagKind, true);
2172+
}
2173+
for (const auto &Mu : SharedLocksToAdd) {
2174+
auto Entry = llvm::make_unique<LockableFactEntry>(Mu, LK_Shared, Loc);
2175+
Entry->setDeclared(true);
2176+
addLock(InitialLockset, std::move(Entry), CapDiagKind, true);
2177+
}
19902178
}
19912179

19922180
for (const auto *CurrBlock : *SortedGraph) {
@@ -2180,11 +2368,20 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) {
21802368
/// at the end of each block, and issue warnings for thread safety violations.
21812369
/// Each block in the CFG is traversed exactly once.
21822370
void runThreadSafetyAnalysis(AnalysisDeclContext &AC,
2183-
ThreadSafetyHandler &Handler) {
2184-
ThreadSafetyAnalyzer Analyzer(Handler);
2371+
ThreadSafetyHandler &Handler,
2372+
BeforeSet **BSet) {
2373+
if (!*BSet)
2374+
*BSet = new BeforeSet;
2375+
ThreadSafetyAnalyzer Analyzer(Handler, *BSet);
21852376
Analyzer.runAnalysis(AC);
21862377
}
21872378

2379+
2380+
void threadSafetyCleanup(BeforeSet* Cache) {
2381+
delete Cache;
2382+
}
2383+
2384+
21882385
/// \brief Helper function that returns a LockKind required for the given level
21892386
/// of access.
21902387
LockKind getLockKindFromAccessKind(AccessKind AK) {

0 commit comments

Comments
 (0)
Please sign in to comment.