Skip to content

Commit

Permalink
Thread safety analysis: Add support for negative requirements, which are
Browse files Browse the repository at this point in the history
capability expressions of the form !expr, and denote a capability that must
not be held.

llvm-svn: 214725
delesley committed Aug 4, 2014
1 parent 0b2ebcb commit 4266522
Showing 5 changed files with 473 additions and 285 deletions.
4 changes: 2 additions & 2 deletions clang/include/clang/Analysis/Analyses/ThreadSafety.h
Original file line number Diff line number Diff line change
@@ -38,9 +38,9 @@ enum ProtectedOperationKind {
/// example, it is an error to write a variable protected by shared version of a
/// mutex.
enum LockKind {
LK_Shared, ///< Shared/reader lock of a mutex.
LK_Shared, ///< Shared/reader lock of a mutex.
LK_Exclusive, ///< Exclusive/writer lock of a mutex.
LK_Generic ///< Can be either Shared or Exclusive
LK_Generic ///< Can be either Shared or Exclusive
};

/// This enum distinguishes between different ways to access (read or write) a
102 changes: 99 additions & 3 deletions clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h
Original file line number Diff line number Diff line change
@@ -24,16 +24,59 @@

#include "clang/Analysis/Analyses/PostOrderCFGView.h"
#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
#include "clang/Analysis/Analyses/ThreadSafetyTraverse.h"
#include "clang/Analysis/AnalysisContext.h"
#include "clang/Basic/OperatorKinds.h"

#include <memory>
#include <ostream>
#include <sstream>
#include <vector>


namespace clang {
namespace threadSafety {


// Various helper functions on til::SExpr
namespace sx {

inline bool equals(const til::SExpr *E1, const til::SExpr *E2) {
return til::EqualsComparator::compareExprs(E1, E2);
}

inline bool matches(const til::SExpr *E1, const til::SExpr *E2) {
// We treat a top-level wildcard as the "univsersal" lock.
// It matches everything for the purpose of checking locks, but not
// for unlocking them.
if (isa<til::Wildcard>(E1))
return isa<til::Wildcard>(E2);
if (isa<til::Wildcard>(E2))
return isa<til::Wildcard>(E1);

return til::MatchComparator::compareExprs(E1, E2);
}

inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) {
auto *PE1 = dyn_cast_or_null<til::Project>(E1);
if (!PE1)
return false;
auto *PE2 = dyn_cast_or_null<til::Project>(E2);
if (!PE2)
return false;
return PE1->clangDecl() == PE2->clangDecl();
}

inline std::string toString(const til::SExpr *E) {
std::stringstream ss;
til::StdPrinter::print(E, ss);
return ss.str();
}

} // end namespace sx



// This class defines the interface of a clang CFG Visitor.
// CFGWalker will invoke the following methods.
// Note that methods are not virtual; the visitor is templatized.
@@ -206,6 +249,59 @@ class CFGWalker {
};




class CapabilityExpr {
// TODO: move this back into ThreadSafety.cpp
// This is specific to thread safety. It is here because
// translateAttrExpr needs it, but that should be moved too.

private:
const til::SExpr* CapExpr; //< The capability expression.
bool Negated; //< True if this is a negative capability

public:
CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {}

const til::SExpr* sexpr() const { return CapExpr; }
bool negative() const { return Negated; }

CapabilityExpr operator!() const {
return CapabilityExpr(CapExpr, !Negated);
}

bool equals(const CapabilityExpr &other) const {
return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr);
}

bool matches(const CapabilityExpr &other) const {
return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr);
}

bool matchesUniv(const CapabilityExpr &CapE) const {
return isUniversal() || matches(CapE);
}

bool partiallyMatches(const CapabilityExpr &other) const {
return (Negated == other.Negated) &&
sx::partiallyMatches(CapExpr, other.CapExpr);
}

std::string toString() const {
if (Negated)
return "!" + sx::toString(CapExpr);
return sx::toString(CapExpr);
}

bool shouldIgnore() const { return CapExpr == nullptr; }

bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); }

bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); }
};



// Translate clang::Expr to til::SExpr.
class SExprBuilder {
public:
@@ -242,10 +338,10 @@ class SExprBuilder {

// Translate a clang expression in an attribute to a til::SExpr.
// Constructs the context from D, DeclExp, and SelfDecl.
til::SExpr *translateAttrExpr(const Expr *AttrExp, const NamedDecl *D,
const Expr *DeclExp, VarDecl *SelfDecl=nullptr);
CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D,
const Expr *DeclExp, VarDecl *SelfD=nullptr);

til::SExpr *translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx);
CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx);

// Translate a clang statement or expression to a TIL expression.
// Also performs substitution of variables; Ctx provides the context.
500 changes: 232 additions & 268 deletions clang/lib/Analysis/ThreadSafety.cpp

Large diffs are not rendered by default.

47 changes: 35 additions & 12 deletions clang/lib/Analysis/ThreadSafetyCommon.cpp
Original file line number Diff line number Diff line change
@@ -105,10 +105,10 @@ inline bool isCalleeArrow(const Expr *E) {
/// \param D The declaration to which the attribute is attached.
/// \param DeclExp An expression involving the Decl to which the attribute
/// is attached. E.g. the call to a function.
til::SExpr *SExprBuilder::translateAttrExpr(const Expr *AttrExp,
const NamedDecl *D,
const Expr *DeclExp,
VarDecl *SelfDecl) {
CapabilityExpr SExprBuilder::translateAttrExpr(const Expr *AttrExp,
const NamedDecl *D,
const Expr *DeclExp,
VarDecl *SelfDecl) {
// If we are processing a raw attribute expression, with no substitutions.
if (!DeclExp)
return translateAttrExpr(AttrExp, nullptr);
@@ -163,26 +163,48 @@ til::SExpr *SExprBuilder::translateAttrExpr(const Expr *AttrExp,

/// \brief Translate a clang expression in an attribute to a til::SExpr.
// This assumes a CallingContext has already been created.
til::SExpr *SExprBuilder::translateAttrExpr(const Expr *AttrExp,
CallingContext *Ctx) {
if (const StringLiteral* SLit = dyn_cast_or_null<StringLiteral>(AttrExp)) {
CapabilityExpr SExprBuilder::translateAttrExpr(const Expr *AttrExp,
CallingContext *Ctx) {
if (!AttrExp)
return CapabilityExpr(nullptr, false);

if (auto* SLit = dyn_cast<StringLiteral>(AttrExp)) {
if (SLit->getString() == StringRef("*"))
// The "*" expr is a universal lock, which essentially turns off
// checks until it is removed from the lockset.
return new (Arena) til::Wildcard();
return CapabilityExpr(new (Arena) til::Wildcard(), false);
else
// Ignore other string literals for now.
return nullptr;
return CapabilityExpr(nullptr, false);
}

bool Neg = false;
if (auto *OE = dyn_cast<CXXOperatorCallExpr>(AttrExp)) {
if (OE->getOperator() == OO_Exclaim) {
Neg = true;
AttrExp = OE->getArg(0);
}
}
else if (auto *UO = dyn_cast<UnaryOperator>(AttrExp)) {
if (UO->getOpcode() == UO_LNot) {
Neg = true;
AttrExp = UO->getSubExpr();
}
}

til::SExpr *E = translate(AttrExp, Ctx);

// Trap mutex expressions like nullptr, or 0.
// Any literal value is nonsense.
if (!E || isa<til::Literal>(E))
return CapabilityExpr(nullptr, false);

// Hack to deal with smart pointers -- strip off top-level pointer casts.
if (auto *CE = dyn_cast_or_null<til::Cast>(E)) {
if (CE->castOpcode() == til::CAST_objToPtr)
return CE->expr();
return CapabilityExpr(CE->expr(), Neg);
}
return E;
return CapabilityExpr(E, Neg);
}


@@ -357,7 +379,8 @@ til::SExpr *SExprBuilder::translateCallExpr(const CallExpr *CE,
LRCallCtx.SelfArg = SelfE;
LRCallCtx.NumArgs = CE->getNumArgs();
LRCallCtx.FunArgs = CE->getArgs();
return translateAttrExpr(At->getArg(), &LRCallCtx);
return const_cast<til::SExpr*>(
translateAttrExpr(At->getArg(), &LRCallCtx).sexpr());
}
}

105 changes: 105 additions & 0 deletions clang/test/SemaCXX/warn-thread-safety-analysis.cpp
Original file line number Diff line number Diff line change
@@ -36,6 +36,9 @@ class __attribute__((lockable)) Mutex {
bool ReaderTryLock() __attribute__((shared_trylock_function(true)));
void LockWhen(const int &cond) __attribute__((exclusive_lock_function));

// for negative capabilities
const Mutex& operator!() const { return *this; }

void AssertHeld() ASSERT_EXCLUSIVE_LOCK();
void AssertReaderHeld() ASSERT_SHARED_LOCK();
};
@@ -4517,3 +4520,105 @@ void test(Opaque* o) {

} // end namespace ScopedLockReturnedInvalid


namespace NegativeRequirements {

class Bar {
Mutex mu;
int a GUARDED_BY(mu);

public:
void baz() EXCLUSIVE_LOCKS_REQUIRED(!mu) {
mu.Lock();
a = 0;
mu.Unlock();
}
};


class Foo {
Mutex mu;
int a GUARDED_BY(mu);

public:
void foo() {
mu.Lock(); // warning? needs !mu?
baz(); // expected-warning {{cannot call function 'baz' while mutex 'mu' is held}}
bar();
mu.Unlock();
}

void bar() {
baz(); // expected-warning {{calling function 'baz' requires holding '!mu'}}
}

void baz() EXCLUSIVE_LOCKS_REQUIRED(!mu) {
mu.Lock();
a = 0;
mu.Unlock();
}

void test() {
Bar b;
b.baz(); // no warning -- in different class.
}
};

} // end namespace NegativeRequirements


namespace NegativeThreadRoles {

typedef int __attribute__((capability("role"))) ThreadRole;

void acquire(ThreadRole R) __attribute__((exclusive_lock_function(R))) __attribute__((no_thread_safety_analysis)) {}
void release(ThreadRole R) __attribute__((unlock_function(R))) __attribute__((no_thread_safety_analysis)) {}

ThreadRole FlightControl, Logger;

extern void enque_log_msg(const char *msg);
void log_msg(const char *msg) {
enque_log_msg(msg);
}

void dispatch_log(const char *msg) __attribute__((requires_capability(!FlightControl))) {}
void dispatch_log2(const char *msg) __attribute__((requires_capability(Logger))) {}

void flight_control_entry(void) __attribute__((requires_capability(FlightControl))) {
dispatch_log("wrong"); /* expected-warning {{cannot call function 'dispatch_log' while mutex 'FlightControl' is held}} */
dispatch_log2("also wrong"); /* expected-warning {{calling function 'dispatch_log2' requires holding role 'Logger' exclusively}} */
}

void spawn_fake_flight_control_thread(void) {
acquire(FlightControl);
flight_control_entry();
release(FlightControl);
}

extern const char *deque_log_msg(void) __attribute__((requires_capability(Logger)));
void logger_entry(void) __attribute__((requires_capability(Logger))) {
const char *msg;

while ((msg = deque_log_msg())) {
dispatch_log(msg);
}
}

void spawn_fake_logger_thread(void) {
acquire(Logger);
logger_entry();
release(Logger);
}

int main(void) {
spawn_fake_flight_control_thread();
spawn_fake_logger_thread();

for (;;)
; /* Pretend to dispatch things. */

return 0;
}

}

0 comments on commit 4266522

Please sign in to comment.