492 lines · cpp
1//===-- BlockInCriticalSectionChecker.cpp -----------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Defines a checker for blocks in critical sections. This checker should find10// the calls to blocking functions (for example: sleep, getc, fgets, read,11// recv etc.) inside a critical section. When sleep(x) is called while a mutex12// is held, other threades cannot lock the same mutex. This might take some13// time, leading to bad performance or even deadlock.14//15//===----------------------------------------------------------------------===//16 17#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"18#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"19#include "clang/StaticAnalyzer/Core/Checker.h"20#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"21#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"22#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"23#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"24#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"25#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"26#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"27#include "llvm/ADT/STLExtras.h"28#include "llvm/ADT/SmallString.h"29#include "llvm/ADT/StringExtras.h"30 31#include <iterator>32#include <utility>33#include <variant>34 35using namespace clang;36using namespace ento;37 38namespace {39 40struct CritSectionMarker {41 const Expr *LockExpr{};42 const MemRegion *LockReg{};43 44 void Profile(llvm::FoldingSetNodeID &ID) const {45 ID.Add(LockExpr);46 ID.Add(LockReg);47 }48 49 [[nodiscard]] constexpr bool50 operator==(const CritSectionMarker &Other) const noexcept {51 return LockExpr == Other.LockExpr && LockReg == Other.LockReg;52 }53 [[nodiscard]] constexpr bool54 operator!=(const CritSectionMarker &Other) const noexcept {55 return !(*this == Other);56 }57};58 59class CallDescriptionBasedMatcher {60 CallDescription LockFn;61 CallDescription UnlockFn;62 63public:64 CallDescriptionBasedMatcher(CallDescription &&LockFn,65 CallDescription &&UnlockFn)66 : LockFn(std::move(LockFn)), UnlockFn(std::move(UnlockFn)) {}67 [[nodiscard]] bool matches(const CallEvent &Call, bool IsLock) const {68 if (IsLock) {69 return LockFn.matches(Call);70 }71 return UnlockFn.matches(Call);72 }73};74 75class FirstArgMutexDescriptor : public CallDescriptionBasedMatcher {76public:77 FirstArgMutexDescriptor(CallDescription &&LockFn, CallDescription &&UnlockFn)78 : CallDescriptionBasedMatcher(std::move(LockFn), std::move(UnlockFn)) {}79 80 [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call, bool) const {81 return Call.getArgSVal(0).getAsRegion();82 }83};84 85class MemberMutexDescriptor : public CallDescriptionBasedMatcher {86public:87 MemberMutexDescriptor(CallDescription &&LockFn, CallDescription &&UnlockFn)88 : CallDescriptionBasedMatcher(std::move(LockFn), std::move(UnlockFn)) {}89 90 [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call, bool) const {91 return cast<CXXMemberCall>(Call).getCXXThisVal().getAsRegion();92 }93};94 95class RAIIMutexDescriptor {96 mutable const IdentifierInfo *Guard{};97 mutable bool IdentifierInfoInitialized{};98 mutable llvm::SmallString<32> GuardName{};99 100 void initIdentifierInfo(const CallEvent &Call) const {101 if (!IdentifierInfoInitialized) {102 // In case of checking C code, or when the corresponding headers are not103 // included, we might end up query the identifier table every time when104 // this function is called instead of early returning it. To avoid this, a105 // bool variable (IdentifierInfoInitialized) is used and the function will106 // be run only once.107 const auto &ASTCtx = Call.getASTContext();108 Guard = &ASTCtx.Idents.get(GuardName);109 }110 }111 112 template <typename T> bool matchesImpl(const CallEvent &Call) const {113 const T *C = dyn_cast<T>(&Call);114 if (!C)115 return false;116 const IdentifierInfo *II =117 cast<CXXRecordDecl>(C->getDecl()->getParent())->getIdentifier();118 if (II != Guard)119 return false;120 121 // For unique_lock, check if it's constructed with a ctor that takes the tag122 // type defer_lock_t. In this case, the lock is not acquired.123 if constexpr (std::is_same_v<T, CXXConstructorCall>) {124 if (GuardName == "unique_lock" && C->getNumArgs() >= 2) {125 const Expr *SecondArg = C->getArgExpr(1);126 QualType ArgType = SecondArg->getType().getNonReferenceType();127 if (const auto *RD = ArgType->getAsRecordDecl();128 RD && RD->getName() == "defer_lock_t" && RD->isInStdNamespace()) {129 return false;130 }131 }132 }133 134 return true;135 }136 137public:138 RAIIMutexDescriptor(StringRef GuardName) : GuardName(GuardName) {}139 [[nodiscard]] bool matches(const CallEvent &Call, bool IsLock) const {140 initIdentifierInfo(Call);141 if (IsLock) {142 return matchesImpl<CXXConstructorCall>(Call);143 }144 return matchesImpl<CXXDestructorCall>(Call);145 }146 [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call,147 bool IsLock) const {148 const MemRegion *LockRegion = nullptr;149 if (IsLock) {150 if (std::optional<SVal> Object = Call.getReturnValueUnderConstruction()) {151 LockRegion = Object->getAsRegion();152 }153 } else {154 LockRegion = cast<CXXDestructorCall>(Call).getCXXThisVal().getAsRegion();155 }156 return LockRegion;157 }158};159 160using MutexDescriptor =161 std::variant<FirstArgMutexDescriptor, MemberMutexDescriptor,162 RAIIMutexDescriptor>;163 164class SuppressNonBlockingStreams : public BugReporterVisitor {165private:166 const CallDescription OpenFunction{CDM::CLibrary, {"open"}, 2};167 SymbolRef StreamSym;168 const int NonBlockMacroVal;169 bool Satisfied = false;170 171public:172 SuppressNonBlockingStreams(SymbolRef StreamSym, int NonBlockMacroVal)173 : StreamSym(StreamSym), NonBlockMacroVal(NonBlockMacroVal) {}174 175 static void *getTag() {176 static bool Tag;177 return &Tag;178 }179 180 void Profile(llvm::FoldingSetNodeID &ID) const override {181 ID.AddPointer(getTag());182 }183 184 PathDiagnosticPieceRef VisitNode(const ExplodedNode *N,185 BugReporterContext &BRC,186 PathSensitiveBugReport &BR) override {187 if (Satisfied)188 return nullptr;189 190 std::optional<StmtPoint> Point = N->getLocationAs<StmtPoint>();191 if (!Point)192 return nullptr;193 194 const auto *CE = Point->getStmtAs<CallExpr>();195 if (!CE || !OpenFunction.matchesAsWritten(*CE))196 return nullptr;197 198 if (N->getSVal(CE).getAsSymbol() != StreamSym)199 return nullptr;200 201 Satisfied = true;202 203 // Check if open's second argument contains O_NONBLOCK204 const llvm::APSInt *FlagVal = N->getSVal(CE->getArg(1)).getAsInteger();205 if (!FlagVal)206 return nullptr;207 208 if ((*FlagVal & NonBlockMacroVal) != 0)209 BR.markInvalid(getTag(), nullptr);210 211 return nullptr;212 }213};214 215class BlockInCriticalSectionChecker : public Checker<check::PostCall> {216private:217 const std::array<MutexDescriptor, 8> MutexDescriptors{218 // NOTE: There are standard library implementations where some methods219 // of `std::mutex` are inherited from an implementation detail base220 // class, and those aren't matched by the name specification {"std",221 // "mutex", "lock"}.222 // As a workaround here we omit the class name and only require the223 // presence of the name parts "std" and "lock"/"unlock".224 // TODO: Ensure that CallDescription understands inherited methods.225 MemberMutexDescriptor(226 {/*MatchAs=*/CDM::CXXMethod,227 /*QualifiedName=*/{"std", /*"mutex",*/ "lock"},228 /*RequiredArgs=*/0},229 {CDM::CXXMethod, {"std", /*"mutex",*/ "unlock"}, 0}),230 FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_lock"}, 1},231 {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}),232 FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_lock"}, 1},233 {CDM::CLibrary, {"mtx_unlock"}, 1}),234 FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_trylock"}, 1},235 {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}),236 FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_trylock"}, 1},237 {CDM::CLibrary, {"mtx_unlock"}, 1}),238 FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_timedlock"}, 1},239 {CDM::CLibrary, {"mtx_unlock"}, 1}),240 RAIIMutexDescriptor("lock_guard"),241 RAIIMutexDescriptor("unique_lock")};242 243 const CallDescriptionSet BlockingFunctions{{CDM::CLibrary, {"sleep"}},244 {CDM::CLibrary, {"getc"}},245 {CDM::CLibrary, {"fgets"}},246 {CDM::CLibrary, {"read"}},247 {CDM::CLibrary, {"recv"}}};248 249 const BugType BlockInCritSectionBugType{250 this, "Call to blocking function in critical section", "Blocking Error"};251 252 using O_NONBLOCKValueTy = std::optional<int>;253 mutable std::optional<O_NONBLOCKValueTy> O_NONBLOCKValue;254 255 void reportBlockInCritSection(const CallEvent &call, CheckerContext &C) const;256 257 [[nodiscard]] const NoteTag *createCritSectionNote(CritSectionMarker M,258 CheckerContext &C) const;259 260 [[nodiscard]] std::optional<MutexDescriptor>261 checkDescriptorMatch(const CallEvent &Call, CheckerContext &C,262 bool IsLock) const;263 264 void handleLock(const MutexDescriptor &Mutex, const CallEvent &Call,265 CheckerContext &C) const;266 267 void handleUnlock(const MutexDescriptor &Mutex, const CallEvent &Call,268 CheckerContext &C) const;269 270 [[nodiscard]] bool isBlockingInCritSection(const CallEvent &Call,271 CheckerContext &C) const;272 273public:274 /// Process unlock.275 /// Process lock.276 /// Process blocking functions (sleep, getc, fgets, read, recv)277 void checkPostCall(const CallEvent &Call, CheckerContext &C) const;278};279 280} // end anonymous namespace281 282REGISTER_LIST_WITH_PROGRAMSTATE(ActiveCritSections, CritSectionMarker)283 284// Iterator traits for ImmutableList data structure285// that enable the use of STL algorithms.286// TODO: Move these to llvm::ImmutableList when overhauling immutable data287// structures for proper iterator concept support.288template <>289struct std::iterator_traits<llvm::ImmutableList<CritSectionMarker>::iterator> {290 using iterator_category = std::forward_iterator_tag;291 using value_type = CritSectionMarker;292 using difference_type = std::ptrdiff_t;293 using reference = CritSectionMarker &;294 using pointer = CritSectionMarker *;295};296 297std::optional<MutexDescriptor>298BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call,299 CheckerContext &C,300 bool IsLock) const {301 const auto Descriptor =302 llvm::find_if(MutexDescriptors, [&Call, IsLock](auto &&Descriptor) {303 return std::visit(304 [&Call, IsLock](auto &&DescriptorImpl) {305 return DescriptorImpl.matches(Call, IsLock);306 },307 Descriptor);308 });309 if (Descriptor != MutexDescriptors.end())310 return *Descriptor;311 return std::nullopt;312}313 314static const MemRegion *skipStdBaseClassRegion(const MemRegion *Reg) {315 while (Reg) {316 const auto *BaseClassRegion = dyn_cast<CXXBaseObjectRegion>(Reg);317 if (!BaseClassRegion || !isWithinStdNamespace(BaseClassRegion->getDecl()))318 break;319 Reg = BaseClassRegion->getSuperRegion();320 }321 return Reg;322}323 324static const MemRegion *getRegion(const CallEvent &Call,325 const MutexDescriptor &Descriptor,326 bool IsLock) {327 return std::visit(328 [&Call, IsLock](auto &Descr) -> const MemRegion * {329 return skipStdBaseClassRegion(Descr.getRegion(Call, IsLock));330 },331 Descriptor);332}333 334void BlockInCriticalSectionChecker::handleLock(335 const MutexDescriptor &LockDescriptor, const CallEvent &Call,336 CheckerContext &C) const {337 const MemRegion *MutexRegion =338 getRegion(Call, LockDescriptor, /*IsLock=*/true);339 if (!MutexRegion)340 return;341 342 const CritSectionMarker MarkToAdd{Call.getOriginExpr(), MutexRegion};343 ProgramStateRef StateWithLockEvent =344 C.getState()->add<ActiveCritSections>(MarkToAdd);345 C.addTransition(StateWithLockEvent, createCritSectionNote(MarkToAdd, C));346}347 348void BlockInCriticalSectionChecker::handleUnlock(349 const MutexDescriptor &UnlockDescriptor, const CallEvent &Call,350 CheckerContext &C) const {351 const MemRegion *MutexRegion =352 getRegion(Call, UnlockDescriptor, /*IsLock=*/false);353 if (!MutexRegion)354 return;355 356 ProgramStateRef State = C.getState();357 const auto ActiveSections = State->get<ActiveCritSections>();358 const auto MostRecentLock =359 llvm::find_if(ActiveSections, [MutexRegion](auto &&Marker) {360 return Marker.LockReg == MutexRegion;361 });362 if (MostRecentLock == ActiveSections.end())363 return;364 365 // Build a new ImmutableList without this element.366 auto &Factory = State->get_context<ActiveCritSections>();367 llvm::ImmutableList<CritSectionMarker> NewList = Factory.getEmptyList();368 for (auto It = ActiveSections.begin(), End = ActiveSections.end(); It != End;369 ++It) {370 if (It != MostRecentLock)371 NewList = Factory.add(*It, NewList);372 }373 374 State = State->set<ActiveCritSections>(NewList);375 C.addTransition(State);376}377 378bool BlockInCriticalSectionChecker::isBlockingInCritSection(379 const CallEvent &Call, CheckerContext &C) const {380 return BlockingFunctions.contains(Call) &&381 !C.getState()->get<ActiveCritSections>().isEmpty();382}383 384void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call,385 CheckerContext &C) const {386 if (isBlockingInCritSection(Call, C)) {387 reportBlockInCritSection(Call, C);388 } else if (std::optional<MutexDescriptor> LockDesc =389 checkDescriptorMatch(Call, C, /*IsLock=*/true)) {390 handleLock(*LockDesc, Call, C);391 } else if (std::optional<MutexDescriptor> UnlockDesc =392 checkDescriptorMatch(Call, C, /*IsLock=*/false)) {393 handleUnlock(*UnlockDesc, Call, C);394 }395}396 397void BlockInCriticalSectionChecker::reportBlockInCritSection(398 const CallEvent &Call, CheckerContext &C) const {399 ExplodedNode *ErrNode = C.generateNonFatalErrorNode(C.getState());400 if (!ErrNode)401 return;402 403 std::string msg;404 llvm::raw_string_ostream os(msg);405 os << "Call to blocking function '" << Call.getCalleeIdentifier()->getName()406 << "' inside of critical section";407 auto R = std::make_unique<PathSensitiveBugReport>(BlockInCritSectionBugType,408 os.str(), ErrNode);409 // for 'read' and 'recv' call, check whether it's file descriptor(first410 // argument) is411 // created by 'open' API with O_NONBLOCK flag or is equal to -1, they will412 // not cause block in these situations, don't report413 StringRef FuncName = Call.getCalleeIdentifier()->getName();414 if (FuncName == "read" || FuncName == "recv") {415 SVal SV = Call.getArgSVal(0);416 SValBuilder &SVB = C.getSValBuilder();417 ProgramStateRef state = C.getState();418 ConditionTruthVal CTV =419 state->areEqual(SV, SVB.makeIntVal(-1, C.getASTContext().IntTy));420 if (CTV.isConstrainedTrue())421 return;422 423 if (SymbolRef SR = SV.getAsSymbol()) {424 if (!O_NONBLOCKValue)425 O_NONBLOCKValue = tryExpandAsInteger(426 "O_NONBLOCK", C.getBugReporter().getPreprocessor());427 if (*O_NONBLOCKValue)428 R->addVisitor<SuppressNonBlockingStreams>(SR, **O_NONBLOCKValue);429 }430 }431 R->addRange(Call.getSourceRange());432 R->markInteresting(Call.getReturnValue());433 C.emitReport(std::move(R));434}435 436const NoteTag *437BlockInCriticalSectionChecker::createCritSectionNote(CritSectionMarker M,438 CheckerContext &C) const {439 const BugType *BT = &this->BlockInCritSectionBugType;440 return C.getNoteTag([M, BT](PathSensitiveBugReport &BR,441 llvm::raw_ostream &OS) {442 if (&BR.getBugType() != BT)443 return;444 445 // Get the lock events for the mutex of the current line's lock event.446 const auto CritSectionBegins =447 BR.getErrorNode()->getState()->get<ActiveCritSections>();448 llvm::SmallVector<CritSectionMarker, 4> LocksForMutex;449 llvm::copy_if(450 CritSectionBegins, std::back_inserter(LocksForMutex),451 [M](const auto &Marker) { return Marker.LockReg == M.LockReg; });452 if (LocksForMutex.empty())453 return;454 455 // As the ImmutableList builds the locks by prepending them, we456 // reverse the list to get the correct order.457 std::reverse(LocksForMutex.begin(), LocksForMutex.end());458 459 // Find the index of the lock expression in the list of all locks for a460 // given mutex (in acquisition order).461 const auto Position =462 llvm::find_if(std::as_const(LocksForMutex), [M](const auto &Marker) {463 return Marker.LockExpr == M.LockExpr;464 });465 if (Position == LocksForMutex.end())466 return;467 468 // If there is only one lock event, we don't need to specify how many times469 // the critical section was entered.470 if (LocksForMutex.size() == 1) {471 OS << "Entering critical section here";472 return;473 }474 475 const auto IndexOfLock =476 std::distance(std::as_const(LocksForMutex).begin(), Position);477 478 const auto OrdinalOfLock = IndexOfLock + 1;479 OS << "Entering critical section for the " << OrdinalOfLock480 << llvm::getOrdinalSuffix(OrdinalOfLock) << " time here";481 });482}483 484void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) {485 mgr.registerChecker<BlockInCriticalSectionChecker>();486}487 488bool ento::shouldRegisterBlockInCriticalSectionChecker(489 const CheckerManager &mgr) {490 return true;491}492