Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -82,6 +82,8 @@ def CloneDetectionAlpha : Package<"clone">, InPackage, Hidden; +def Magenta : Package<"magenta">; + //===----------------------------------------------------------------------===// // Core Checkers. //===----------------------------------------------------------------------===// @@ -722,3 +724,14 @@ } // end "clone" +//===----------------------------------------------------------------------===// +// Magenta checkers. +//===----------------------------------------------------------------------===// + +let ParentPackage = Magenta in { + +def SpinLockChecker : Checker<"SpinLock">, + HelpText<"Check for correct handling of spinlocks">, + DescFile<"SpinLockChecker.cpp">; + +} // end "magenta" Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt =================================================================== --- lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -70,6 +70,7 @@ ReturnPointerRangeChecker.cpp ReturnUndefChecker.cpp SimpleStreamChecker.cpp + SpinLockChecker.cpp StackAddrEscapeChecker.cpp StdLibraryFunctionsChecker.cpp StreamChecker.cpp Index: lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp @@ -0,0 +1,198 @@ +//== SpinLockChecker.cpp - SpinLock checker ---------------------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This defines SpinLockChecker, a check for the Magenta kernel. It +// checks that there are no execution paths where spinlocks are locked +// twice in a row, or unlocked twice in a row. +// +//===----------------------------------------------------------------------===// + +#include "ClangSACheckers.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/CheckerManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" +#include "llvm/ADT/SmallString.h" + +using namespace clang; +using namespace ento; + +namespace { + +typedef llvm::SmallString<16> ErrorCategoryStr; +typedef llvm::SmallString<32> FunctionNameStr; + +struct LockInfo { + + enum Kind { Locked, Released } K; + + LockInfo(Kind kind) : K(kind) {} + + bool operator==(const LockInfo &LI) const { return K == LI.K; } + + void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); } + + bool isLocked() const { return K == Locked; } + + bool isReleased() const { return K == Released; } + + static LockInfo getLocked() { return LockInfo(Locked); } + + static LockInfo getReleased() { return LockInfo(Released); } + + static ErrorCategoryStr getLockErrorCategory() { return LockErrCategory; } + + static FunctionNameStr getSpinLockFuncName() { return SpinLockFuncName; } + + static FunctionNameStr getSpinUnlockFuncName() { return SpinUnlockFuncName; } + +private: + static const ErrorCategoryStr LockErrCategory; + static const FunctionNameStr SpinLockFuncName; + static const FunctionNameStr SpinUnlockFuncName; +}; + +const ErrorCategoryStr LockInfo::LockErrCategory("Lock Error"); +const FunctionNameStr LockInfo::SpinLockFuncName("spin_lock"); +const FunctionNameStr LockInfo::SpinUnlockFuncName("spin_unlock"); +} + +/// We keep track of the locks in a map. SpinLockMap maps the +/// memory region of a spinlock to its status (locked, released). +/// The reason that we keep track of spinlocks as memory region is +/// that the lock/unlock functions take lock arguments as pointers. +REGISTER_MAP_WITH_PROGRAMSTATE(SpinLockMap, const MemRegion *, LockInfo) + +namespace { + +class SpinLockChecker : public Checker { + + /// When facing a spin_unlock function call, check the record of the + /// corresponding lock in SpinLockMap and make sure that there are no + /// problems such as double unlocks. + void processSpinUnlockCall(const CallEvent &Call, CheckerContext &C, + const MemRegion *SpinLockLocation) const; + + /// When facing a spin_lock function call, check the record of the + /// corresponding lock in SpinLockMap and make sure that there are no + /// problems such as double locks. + void processSpinLockCall(const CallEvent &Call, CheckerContext &C, + const MemRegion *SpinLockLocation) const; + void reportDoubleLock(const CallEvent &Call, CheckerContext &C, + const MemRegion *Mem) const; + void reportDoubleUnlock(ExplodedNode *Node, CheckerContext &C, + const MemRegion *Mem) const; + std::unique_ptr DoubleLockBugType; + std::unique_ptr DoubleUnlockBugType; + +public: + SpinLockChecker(); + void checkPreCall(const CallEvent &Call, CheckerContext &C) const; +}; +} + +void ento::registerSpinLockChecker(CheckerManager &Mgr) { + Mgr.registerChecker(); +} + +SpinLockChecker::SpinLockChecker() { + DoubleLockBugType.reset( + new BugType(this, "Double SpinLock", LockInfo::getLockErrorCategory())); + + DoubleUnlockBugType.reset( + new BugType(this, "Double SpinUnlock", LockInfo::getLockErrorCategory())); +} + +/// Run the necessary processing before a spin_lock/spin_unlock function call +void SpinLockChecker::checkPreCall(const CallEvent &Call, + CheckerContext &C) const { + if (!Call.getCalleeIdentifier()) + return; + + FunctionNameStr CalleeName = Call.getCalleeIdentifier()->getName(); + if (CalleeName != LockInfo::getSpinLockFuncName() && + CalleeName != LockInfo::getSpinUnlockFuncName()) + return; + + if (Call.getNumArgs() == 0) + return; + + // Memory region of the spinlock + const MemRegion *SpinLockLocation = Call.getArgSVal(0).getAsRegion(); + // If SpinLockLocation is NULL, this is likely due to changes in the + // signature of spin_lock/spin_unlock functions, and we have to update + // the checker accordingly. For now, we terminate with an error + // message. + if (!SpinLockLocation) + llvm_unreachable("No spinlock pointer passed to spin_lock/spin_unlock!"); + + if (CalleeName == LockInfo::getSpinLockFuncName()) + processSpinLockCall(Call, C, SpinLockLocation); + else + processSpinUnlockCall(Call, C, SpinLockLocation); +} + +void SpinLockChecker::processSpinLockCall( + const CallEvent &Call, CheckerContext &C, + const MemRegion *SpinLockLocation) const { + ProgramStateRef St = C.getState(); + const LockInfo *LI = St->get(SpinLockLocation); + if (LI && LI->isLocked()) { + // This spinlock has been locked before! + reportDoubleLock(Call, C, SpinLockLocation); + return; + } + + St = St->set(SpinLockLocation, LockInfo::getLocked()); + C.addTransition(St); +} + +void SpinLockChecker::processSpinUnlockCall( + const CallEvent &Call, CheckerContext &C, + const MemRegion *SpinLockLocation) const { + ProgramStateRef St = C.getState(); + const LockInfo *LI = St->get(SpinLockLocation); + if (LI && LI->isReleased()) { + // Unlocking a key twice! Does not cause an error, but may be an + // indication of an incorrect logic (maybe the spinlock was supposed to + // be locked again before the second unlocking attempt). + ExplodedNode *Node = C.generateNonFatalErrorNode(St); + if (!Node) + return; + reportDoubleUnlock(Node, C, SpinLockLocation); + } + + St = St->set(SpinLockLocation, LockInfo::getReleased()); + C.addTransition(St); +} + +void SpinLockChecker::reportDoubleUnlock( + ExplodedNode *Node, CheckerContext &C, + const MemRegion *SpinLockLocation) const { + auto Report = llvm::make_unique( + *DoubleUnlockBugType, + "Execution path found where spinlock is unlocked twice in a row", Node); + Report->markInteresting(SpinLockLocation); + C.emitReport(std::move(Report)); +} + +void SpinLockChecker::reportDoubleLock( + const CallEvent &Call, CheckerContext &C, + const MemRegion *SpinLockLocation) const { + ExplodedNode *Node = C.generateErrorNode(); + if (!Node) + return; + + auto Report = llvm::make_unique( + *DoubleLockBugType, + "Execution path found where spinlock is locked twice in a row", Node); + Report->addRange(Call.getSourceRange()); + Report->markInteresting(SpinLockLocation); + C.emitReport(std::move(Report)); +} Index: test/Analysis/spinlock_correct.c =================================================================== --- /dev/null +++ test/Analysis/spinlock_correct.c @@ -0,0 +1,30 @@ +// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s +// expected-no-diagnostics + +typedef unsigned int lock_t; + +static lock_t l; + +void spin_lock(lock_t *lock); +void spin_unlock(lock_t *lock); +int bar(); + +int foo() { + int a = bar(); + if (a > 0) { + spin_lock(&l); + } + + if (a < -10) { + spin_lock(&l); + } + + if (a > 0) + spin_unlock(&l); + + if (a < -10) + spin_unlock(&l); + + return 0; +} + Index: test/Analysis/spinlock_double_lock.c =================================================================== --- /dev/null +++ test/Analysis/spinlock_double_lock.c @@ -0,0 +1,20 @@ +// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s + +typedef unsigned int lock_t; + +static lock_t l; + +void spin_lock(lock_t *lock); +void spin_unlock(lock_t *lock); +int bar(); + +int foo() { + int a = bar(); + if (a > 0) + spin_lock(&l); + if (a > 10) + spin_lock(&l); // expected-warning{{Execution path found where spinlock is locked twice in a row}} + + return 0; +} + Index: test/Analysis/spinlock_double_release.c =================================================================== --- /dev/null +++ test/Analysis/spinlock_double_release.c @@ -0,0 +1,35 @@ +// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s + +typedef unsigned int lock_t; + +typedef struct S { + int a; + lock_t l; +} S_t; + +static S_t st; + +void spin_lock(lock_t *lock); +void spin_unlock(lock_t *lock); +int bar(); + +void bar1(lock_t *y) { + spin_unlock(y); +} + +void bar2(lock_t *x) { + spin_unlock(x); // expected-warning{{Execution path found where spinlock is unlocked twice in a row}} +} + +int foo() { + int a = bar(); + if (a > 0) { + spin_lock(&st.l); + bar1(&st.l); + } + + lock_t *c = &st.l; + bar2(c); + return 0; +} +